锐客网

  1. 首页 > 睿知 > >

背包问题 背包哪里有

生活知识睿知

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

    推荐阅读


    上一篇：腹股沟在哪里 阴部是哪里

    下一篇：艾条对蟑螂有用吗