背包问题背包哪里有

写在前面
问题描述有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

背包问题 背包哪里有

背包问题背包哪里有