PHP动态规划解决0-1背包问题实例分析

这篇文章主要介绍了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程序设计有所帮助。