【DP】0-1 背包问题｜Java 刷题打卡

本文正在参加「Java主题月 – Java 刷题打卡」，详情查看活动链接

一、题目概述

题目：0-1 背包问题

给你一个可装载重量为 W 的背包和 N 个物品，每个物品有重量和价值两个属性。其中第 i 个物品的重量为 wt[i], 价值为 val[i]，现在让你用这个背包装物品，最多能装的价值是多少？

示例1：

输入：
N = 3（物品）, W = 4（重量）
wt = [2, 1, 3]
val = [4, 2, 3]

输出：6
复制代码

题干分析

这个题目中的物品不可以分割，要么装进包里，要么不装，不能说切成两块装一部分。

动态规划标准套路：

1. 第一步要明确：状态 和 选择
2. 第二步要明确：dp 数组的定义
3. 第三步：根据 “选择”，思考状态转移的逻辑

1. 第一步要明确：状态 和 选择

只要给定几个物品和一个背包的容量限制，就形成了一个背包问题。

1. 状态有两个：“背包的容量” 和 “可选择的物品”

2. 选择就是：“装进背包” 或者 “不装进背包”

框架如下：

for 状态1 in 状态1的所有取值：
    for 状态2 in 状态2的所有取值：
        for ...
            dp[状态1][状态2][...] = 计算(选择1，选择2...)
复制代码

2. 第二步要明确：dp 数组的定义

因为 “状态” 有两个，也就是说需要一个二维 dp 数组。

1. dp[i][w] 的定义如下：对于前 i 个物品，当前背包的容量为 w，这种情况下可以装的最大价值是 dp[i][w]

举个栗子：
dp[3][5] = 6 含义是：对于给定的一系列物品，若只对前 3 个物品进行选择，当背包容量为 5 时，最多可以装下的价值为 6

2. 想求的最终答案就是：dp[N][W]

3. base case：dp[0][..] = d[..][0] = 0

因为没有物品或者背包没有空间的时候，能g转的最大价值是 0

3. 第三步：根据 “选择”，思考状态转移的逻辑

1. 如果没有把这个第 i 个物品装入背包：最大价值 dp[i][w] = dp[i-1][w] ，继承之前的结果

2. 如果把这第 i 个物品装入背包：那么 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 个物品的价值val[i-1]

细化后：

for (int i = 1; i <= N; ++i) {
    for (int w = 1; w <= W; ++w) {
        dp[i][w] = Math.max(dp[i - 1][w], dp[i-1][w - wt[i - 1]] + val[i - 1]);
    }
}

return dp[N][W];
复制代码

二、思路实现

int knaspsack(int W, int N, int[] wt, int[] val) {
    
    // base case 已初始化
    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 - 1] < 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];
}
复制代码