回帖：用动态规划来解背包问题
在历届NOIP竞赛中，有4道初赛题和5道复赛题均涉及到背包问题，所谓的背包问题，可以描述如下：一个小偷打劫一个保险箱，发现柜子里有N类不同大小与价值的物品，但小偷只有一个容积为M的背包来装东西，背包问题就是要找出一个小偷选择所偷物品的组合，以使偷走的物品总价值最大。
如有4件物品，容积分别为： 3 4 5 8
对应的价值分别为： 4 5 7 10
小偷背包的载重量为：12
则取编号为1 2 3的物品，得到最大价值为16。
算法分析：如果采用贪心法，则先取价值最大的10，消耗了容积8，下面只能取容积为4的物品，得到价值5，这样总价值是15，这不是最优解，因此贪心法是不正确的。
采用穷举法，用一个B数组来表示取数的标记，当B=0时表示第i件物品不取，当B=1时表示第i件物品已取，初始化全部取0，以下算法是从后面的物品开始取起，通过B数组的取值把15种取法全部穷举出来，价值MAX初始化为0。
B[0] B[1] B[2] B[3] B[4]
0 0 0 0 0 {初始化}
0 0 0 0 1 {取第4件物品，容积为8，不超，价值为10，将MAX替换为10}
0 0 0 1 0 ｛取物品3，容积为5，不超，价值为7，不换｝
0 0 0 1 1 ｛取物品3、4，容积为13，超｝
0 0 1 0 0 ｛取物品2，容积为4，不超，价值为5，不换｝
0 0 1 0 1
0 0 1 1 0
0 0 1 1 1
……
0 1 1 1 0 ｛这是最佳方案｝
0 1 1 1 1
1 0 0 0 0 ｛当B〔0〕＝1时停止，B〔0〕称为哨兵｝
生成B数组中数据的方法如下：
fillchar(b,sizeof(b),0);
while b[0]=0 do
begin j:=n;
while b=1 do dec(j);
b:=1;
for i:=j+1 to n do
b:=0;
end；
小结：以上每件物品只能取1件，所以取法只有0和1两种情况，我们称之为0、1背包，算法的时间�