0-1背包问题动态规划详解及代码.docx

0/1背包问题动态规划详解及C 代码动态规划是用空间换时间的一种方法的抽象。其关键是发现子问题和记录其结果。然后 利用这些结果减轻运算量。比如 01 背包问题。/*一个旅行者有一个最多能用M公斤的背包，现在有N件物品， 它们的重量分别是W1， W2， .,Wn,它们的价值分别为P1,P2,.,Pn. 若每种物品只有一件求旅行者能获得最大总价值。 输入格式：M,N W1,P1 W2,P2.输出格式：X*/因为背包最大容量M未知。所以，我们的程序要从1 到 M一个一个的试。比如，开始任选N 件物品的一个。看对应M的背包，能不能放进去，如果能放进去，并且还有多的空间，则， 多出来的空间里能放N-1 物品中的最大价值。怎么能保证总选择是最大价值呢？看下表。 测试数据：10,33,44,55,6cij数组保存了1,2,3号物品依次选择后的最大价值.这个最大价值是怎么得来的呢?从背包