写在前面 问题描述
有n件物品和一个最多能称重w的背包。一篇文章只有两个属性:权重和价值。第I项的权重为weight[i]，得到的值为value[i]。每个项目只能使用一次。找出哪些物品放入背包，物品总价值更大。
注意:0-1背包问题不能用贪心算法解决，也就是说不能先把性价比更高的物品加起来优化。这是因为这种方法可能会造成背包空的浪费，从而无法优化。
基本想法这里有两个变量体积和值。我们定义dp[i][j]是指第I项的体积不超过J所能达到的更大值。设第I个物品的体积为W，取值为v，根据第I个物品是否加入背包，可以分两种情况讨论:
物品I没有加入背包，更大值:dp[i][j] = dp[i-1][j]。
背包中加入物品I:DP[I][J]= DP[I-1][J-W]v。
可以添加或不添加项目I，取决于哪种情况下的更大值更大。因此，0-1背包的状态转移方程为:
dp[i][j] = max(dp[i - 1][j]，dp[i - 1][j - w] v)
代码实现 //W为背包总重量//N为物品数量//weights数组存储N个物品的重量//values数组存储N个物品的价值publicintknapsack(intW,intN,int[]weights,int[]values){//dp[i][0]和dp[0][j]没有价值已经初始化0int[][]dp=newint[N 1][W 1];//从dp[1][1]开始遍历填表for(inti=1;i
