背包问题描述如下:
有编号分别为a,b,c,d,e的五件物品，它们的重量分别是4,2,6,5,3，它们的价值分别是6,3,5,4,6，现在给你个承重为10的背包，如何让背包里装入的物品具有最大的价值总和？
对于这题我们先不解题。先扯扯动态规划，下面描述的不太详细，可以自行百度:
动态规划所处理的问题是一个多阶段决策问题，一般由初始状态开始，通过对中间阶段决策的选择，达到结束状态。这些决策形成了一个决策序列，同时确定了完成整个过程的一条活动路线(通常是求最优的活动路线)。动态规划的设计都有着一定的模式，一般要经历以下几个步骤。
初始状态→│决策１│→│决策２│→…→│决策ｎ│→结束状态
解题公式:f(n,m)=max{f(n-1,m), f(n-1,m-w[n])+P(n,m)}
这个一开始肯定是懵懂的，不要被这些公式和概念吓到。现在我们开始解题:
1.首先是初始状态。 假如只有a物品假如包重量为1-10分别能装多大价值物品
| 物品 | 重量 | 价值 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| a | 4 | 6 | 0 | 0 | 0 | 6 | 6 | 6 | 6 | 6 | 6 | 6 |
因为此时只算上了一个a物品,包各个重量的最大价值已经算出来了。这就是动态规划的初始状态。
2. 中间各种决策。上一步得到了只有a物品的情况下包各个重量下的最大价值，现在我们来决策1，就在第一步基础上增加b物件，现在我们有2个物品，再看看包各个重量的最大价值
| 物品 | 重量 | 价值 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| a | 4 | 6 | 0 | 0 | 0 | 6 | 6 | 6 | 6 | 6 | 6 | 6 |
| b | 2 | 3 | 0 | 3 | 3 | 6 | 6 | 9 | 9 | 9 | 9 | 9 |
这里b4详细计算的。根据上面2个公式我只用取2个值的最大值。这2个值分别为a4和a(4-2(b的重量))+3(b的价值)。计算后分别为6和3,我们取最大值6。这步是所有理解的关键。
于是我们有决策2(同样的方式将c物品放进来计算),决策3(将d物品放进来),决策4(将e物品放进来)
3.走完所有决策后，于是我们有最终方案了，包各个重量的最大价值即为最后将e物品放进来的那一行。
理论说完我们直接上代码，这里是php版本代码，看了下网上例子，几乎很少有php版本的代码，感觉有点歧视php。作为多年php开发经验，再加上php毕竟世界上最好的语言，哈哈。开个玩笑!
<?php//初始化各个物品重量和价值数组$weight_arr = array(0,4,2,6,5,3);$value_arr = array(0,6,3,5,4,6);//设置包最大重量为10$bag_max = 10;$items = count($weight_arr) - 1;$cache_map = array();$cache_map[] = array_fill(1, $items, 0);$ik = 1;//初始状态,假如只有第一个物品包各个重量的最大价值for($i = 1; $i <= $bag_max; $i++){ if($weight_arr[$ik] > $i) { $cache_map[$ik][$i] = 0; } else { $cache_map[$ik][$i] = $value_arr[$ik]; } }//中间的各种决策(依次放入物品b,c,d,e)for($i = 1; $i <= $bag_max; $i++) for($j = 2; $j <= $items; $j++) { $j_weight = $weight_arr[$j]; $j_value = $value_arr[$j]; $j_prev_value = $cache_map[$j-1][$i]; if($j_weight > $i) { $cache_map[$j][$i] = $j_prev_value; } else { $j_extra_value = $j_value + $cache_map[$j-1][$i-$j_weight]; $cache_map[$j][$i] = max($j_prev_value, $j_extra_value); } } //最终状态for($i = 1; $i <= $bag_max; $i++){ echo $i . ':' . $cache_map[$items][$i] . PHP_EOL;}最后显示下计算结果吧:
1:02:33:64:65:96:97:128:129:1510:15
动态规划之背包问题实现php
原文地址：http://blog.51cto.com/chinalx1/2109247