1.确定状态变量（函数）
2.确定状态转移方程（递推关系）
3.确定边界
1.状态变量：f[i][j]表示前i件物品放入容量为j的背包的最大价值
2.当背包容量等j的时候我们要考虑第i件物品能否放入？是否放入？
3.如果j<w[i]的时候表示背包容量不够，这个时候背包最大价值应该等于容量等于j的时候前i-1件物品在背包容量等于j的时候最大价值f[i][j]=f[i-1][j]
4.当背包容量j>=w[i]的时候，分为两种情况
（1）不放
当第i件物品不放入的时候f[i][j]=f[i-1][j]
（2）放入
当第i件物品放入背包的时候，f[i][j]=f[i-1][j-w[i]]+v[i]，解释一下j-w[i]，这个时候是需要放入第i件物品那么第i件物品需要占用的空间就是w[i]，这个时候背包容量等于j第i件物品占用w[i]就只剩下 j-w[i]，剩下的空间就是留给前i-1件物品，所以我们需要知道f[i-1][j-w[i]]的最大价值加上第i件物品的价值。这就是为什么等于f[i][j]=f[i-1][j-w[i]]+v[i]
最后我们需要选取两种选择的最大值f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i])
1.当背包容量等于0的时候或者物品数量等于0的时候价值等于0
找出几个位置进行解释
f[1][2]=3
表示第1件物品放入容量等于2的背包最大价值等于3
这个时候背包容量等于2刚好第一件物品重量等于2可以知道我们第1件物品可以放入这个时候背包价值f[i][j]=f[i-1][j-w[i]]+v[i]，表示第0个物品容量等于2的时候价值加上我们放入这件物品的价值
f[2][3]=4
根据f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i])，我们可以知道这个时候放入第二件物品的价值会更大。
f[2][5]=7
我们是判断不放入的时候价值f[1][5]=3和放入的时候我们先找到f[1][5-3]的最大价值然后加上现在物品的价值f[i-1][j-w[i]]+v[i]=7，这种情况我们当然选择放入价值更大所以f[2][5]=7
最后f[4][8]=12，就表示4件物品放入背包容量等于8的最大价值
【题目描述】
一个旅行者有一个最多能装 M公斤的背包，现在有 n 件物品，它们的重量分别是W1，W2，…,Wn,它们的价值分别为C1,C2,…,Cn，求旅行者能获得最大总价值。
【输入】
第一行：两个整数，M(背包容量，M<=200)和N(物品数量，N<=30)；第2…N+1
行：每行二个整数Wi，Ci，表示每个物品的重量和价值。
【输出】
仅一行，一个数，表示最大总价值。
【输入样例】
10 4
2 1
3 3
4 5
7 9
【输出样例】
12
仅供参考！
版权声明：
本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。
本文网址：https://www.mushiming.com/mjsbk/14709.html