這篇文章主要介紹了PHP動態規劃解決0-1背包問題,實例分析了背包問題的原理與實現技巧,需要的朋友可以參考下

本文實例分析了PHP動態規劃解決0-1背包問題。分享給大家供大家參考。具體分析如下：

背包問題描述：一個承受最大重量為W的背包，現在有n個物品，每個物品重量為t, 每個物品的價值為v。

要使得這個背包重量最大(但不能超過W),同時又需要背包的價值最大。

思路：定義一個二維數組，一維為物品數量(表示每個物品),二維是重量(不超過最大,這里是15),下面數組a,

動態規劃原理思想，max(opt(i-1,w),wi+opt(i-1,w-wi)) 當中最大值，

opt(i-1,w-wi)指上一個最優解

1. <?php 
2. //這是我根據動態規劃原理寫的 
3. // max(opt(i-1,w),wi+opt(i-1,w-wi)) 
4. //背包可以裝最大的重量 
5. $w=15; 
6. //這里有四件物品,每件物品的重量 
7. $dx=array(3,4,5,6); 
8. //每件物品的價值 
9. $qz=array(8,7,4,9); 
10. //定義一個數組 
11. $a=array(); 
12. //初始化 
13. for($i=0;$i<=15;$i++){ $a[0][$i]=0; } 
14. for ($j=0;$j<=4;$j++){ $a[$j][0]=0; } 
15. //opt(i-1,w),wi+opt(i-1,w-wi) 
16. for ($j=1;$j<=4;$j++){ 
17. for($i=1;$i<=15;$i++){ 
18. $a[$j][$i]=$a[$j-1][$i]; 
19. //不大于最大的w=15 
20. if($dx[$j-1]<=$w){ 
21. if(!isset($a[$j-1][$i-$dx[$j-1]])) continue; 
22. //wi+opt(i-1,wi) 
23. $tmp = $a[$j-1][$i-$dx[$j-1]]+$qz[$j-1]; 
24. //opt(i-1,w),wi+opt(i-1,w-wi) => 進行比較  
25. if($tmp>$a[$j][$i]){ 
26. $a[$j][$i]=$tmp; 
27. } 
28. } 
29. } 
30. } 
31. //打印這個數組,輸出最右角的值是可以最大價值的 
32. for ($j=0;$j<=4;$j++){ 
33. for ($i=0;$i<=15;$i++){ 
34. echo $a[$j][$i]."/t"; 
35. } echo "/n"; 
36. } 
37. ?> 

希望本文所述對大家的php程序設計有所幫助。