0-1背包问题基础版

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];
    }
}