写在前

问题描述

有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]没有价值已经初始化0 int[][]dp=newint[N 1][W 1]; //从dp[1][1]开始遍历填表 for(inti=1;i