0-1背包问题基础版

约定不等于承诺〃 2023-10-05 19:41 48阅读 0赞

#### 0-1背包问题基础版 ####

*  一些概念
 *  题目
 *  解题思路
 *  代码

## 一些概念 ##

*  0-1 背包一个物品只能用一次
 *  完全背包：物品数量为无限个
 *  多重背包：物品数量有限制
 *  多维费用背包：物品不仅有重量，还有体积，同时考虑这两种限制
 *  其它：物品之间相互约束或者依赖

## 题目 ##

有一个容量为 N 的背包，要用这个背包装下物品的价值最大，这些物品有两个属性：体积 w 和价值 v。  
其中第i个物品的的重量为wt\[i\]，价值为val\[i\]。现在你用这个背包装物品，最多能装的价值是多少？

例如：
    N=3,W=4
    wt=[2,1,3]
    val=[4,2,3]
    算法返回6，选择前两件物品放入背包，总重量3<W，可以获得最大价值为6

## 解题思路 ##

1.  该题有两个状态，背包的剩余体积，可以选的物品，所以我们需要一个二维的dp数组
2.  dp数组含义：`dp[i][w]`：对于前i个物品，当前背包容量为w，这种情况下可以装的最大价值
3.  base case：`dp[0][..]=0、dp[...][0]=0`即没有物品或者背包容量为0的时候，能装的最大价值就是0.
4.  我们要的结果就是`dp[N][W]`所以需要正向遍历
5.  对于每个物品只有选择装入或者不装入背包这两种情况。
    
    1.  不装入那么最大价值`dp[i][w]`就是继承之前的结果`dp[i-1][w]`
    2.  装入那么`dp[i][w]`就是`dp[i - 1][(w-wt[i - 1])] + val[i - 1]`。`dp[i - 1][(w-wt[i - 1])]`很好理解，如果装入了第i个物品，那么背包剩余重量就是`w-wt[i - 1]`，我们就要寻找在该限制下前`i-1`个物品的最大价值`dp[i - 1][(w-wt[i - 1])]`，加上该物品的最大价值`val[i - 1]`

## 代码 ##

public class 零一背包基础版 {
        
    
    
        /**
         * @param W   背包总体积
         * @param N   物品数量
         * @param wt  数组存储 N 个物品的重量
         * @param val 数组存储 N 个物品的价值
         * @return
         */
        public int knapsack(int W, int N, int[] wt, int[] val) {
        
            //dp[i][w]：对于前i个物品，当前背包容量为w，这种情况下可以装的最大价值
            //base case ：已经初始化为0了
            int[][] dp = new int[N + 1][W + 1];
            for (int i = 1; i <= N; i++) {
        
                for (int w = 1; w < W; w++) {
        
                    if (w - wt[i] < 0) {
        
                        //背包容量不够了，只能选择不放入背包
                        dp[i][w] = dp[i - 1][w];
                    } else {
        
                        //装入或不装入背包，择优
                        dp[i][w] = Math.max(dp[i - 1][(w-wt[i - 1])] + val[i - 1], dp[i - 1][w]);
                    }
                }
            }
            return dp[N][W];
        }
    }