背包哪里有(背包问题)

写在前面

问题描述

有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

以上就是由优质生活领域创作者 深圳生活网小编 整理编辑的，如果觉得有帮助欢迎收藏转发~