「代码随想录算法训练营」第三十二天 | 动态规划 part5

2024-08-08 09:10 由云雀AC了一整天发表于 #其他

52. 携带研究材料

题目链接：https://kamacoder.com/problempage.php?pid=1052
文章讲解：https://programmercarl.com/背包问题理论基础完全背包.html
视频讲解：https://www.bilibili.com/video/BV1uK411o7c9/
题目状态：看题解过

思路：

在0-1背包问题中，每个物品只能选择一次，即每个物品要么被完全放入背包，要么完全不放入。内循环从大到小遍历的原因主要是为了贪心选择，即每次选择当前价值最大的物品。这样做的目的是为了在有限的背包容量下尽可能多地装入价值高的物品。如果背包容量不足以放入当前价值最大的物品，就跳过这个物品，继续考虑下一个价值稍低的物品。这种策略可以保证在给定的背包容量下获得最大的总价值。

for(int i = 0; i < weight.size(); i++) { // 遍历物品
    for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    }
}

而在完全背包问题中，每个物品可以放入背包任意多次。内循环从小到大遍历的原因是，由于每个物品可以重复使用，我们希望首先考虑价值较低的物品，看是否能够用较少的背包容量达到接近目标价值的状态。这样，当我们考虑价值较高的物品时，可以更有效地利用背包的剩余容量，从而可能获得更高的总价值。

// 先遍历物品，再遍历背包
for(int i = 0; i < weight.size(); i++) { // 遍历物品
    for(int j = weight[i]; j <= bagWeight ; j++) { // 遍历背包容量
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    }
}

代码：

#include <iostream>
#include <vector>
using namespace std;

// 先遍历背包，再遍历物品
void test_CompletePack(vector<int> weight, vector<int> value, int bagWeight) {

    vector<int> dp(bagWeight + 1, 0);

    for(int j = 0; j <= bagWeight; j++) { // 遍历背包容量
        for(int i = 0; i < weight.size(); i++) { // 遍历物品
            if (j - weight[i] >= 0) dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }
    cout << dp[bagWeight] << endl;
}
int main() {
    int N, V;
    cin >> N >> V;
    vector<int> weight;
    vector<int> value;
    for (int i = 0; i < N; i++) {
        int w;
        int v;
        cin >> w >> v;
        weight.push_back(w);
        value.push_back(v);
    }
    test_CompletePack(weight, value, V);
    return 0;
}

518. 零钱兑换 II

题目链接：https://leetcode.cn/problems/coin-change-ii/
文章讲解：https://programmercarl.com/0518.零钱兑换II.html
题目难度：中等
视频讲解：https://www.bilibili.com/video/BV1KM411k75j/
题目状态：过

思路：

完全背包问题，dp[j] 数组表示总金额为 j 的时候有几种不同的组合，因此 j+1 的组合情况就是在 j 的组合情况中加 1，因此 dp[j] 的构建方式就出来了：

dp[j] += dp[j - coins[i]];

代码：

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount + 1, 0);
        dp[0] = 1;
        for(int i = 0; i < coins.size(); ++i) {
            for(int j = coins[i]; j <= amount; ++j) {
                dp[j] += dp[j - coins[i]];
            }
        }
        return dp[amount];
    }
};

377. 组合总和 IV

题目链接：https://leetcode.cn/problems/combination-sum-iv/
文章讲解：https://programmercarl.com/0377.组合总和Ⅳ.html
题目难度：中等
视频讲解：https://www.bilibili.com/video/BV1V14y1n7B6/
题目状态：看题解过

思路：

将“背包”放在外围循环，将“物品”放在内围循环，这样的话，每次循环都会重新遍历一遍“物品”，可以将不同的排列顺序加入组合中，如下示例：

假设 nums = [1, 2]，target = 3。我们需要计算所有可能的组合。

初始化：dp[0] = 1，因为只有一种方法可以得到和为 0，即不选任何数字。
计算:
- 目标和为 1：
  - 使用 1：dp[1] += dp[0]，所以 dp[1] = 1。
- 目标和为 2：
  - 使用 1：dp[2] += dp[1]，所以 dp[2] = 1。
  - 使用 2：dp[2] += dp[0]，所以 dp[2] = 2。
- 目标和为 3：
  - 使用 1：dp[3] += dp[2]，所以 dp[3] = 2。
  - 使用 2：dp[3] += dp[1]，所以 dp[3] = 3。
组合路径：
- 和为 1：
  [1]
- 和为 2：
  [1, 1]
  [2]
- 和为 3：
  [1, 1, 1]
  [1, 2]
  [2, 1]

通过上面的遍历，即可得到所有排列。

代码：

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<int> dp(target + 1, 0);
        dp[0] = 1;
        for(int i = 0; i <= target; ++i) {
            for(int j = 0; j < nums.size(); ++j) {
                if(i - nums[j] >= 0 && dp[i] < INT_MAX - dp[i - nums[j]])
                    dp[i] += dp[i - nums[j]];
            }
        }
        return dp[target];
    }
};

70. 爬楼梯

题目链接：https://kamacoder.com/problempage.php?pid=1067
文章讲解：https://programmercarl.com/0070.爬楼梯完全背包版本.html
题目状态：过

思路：

这题的思路和上一题一样：计算当前 dp 的时候要把比当前 dp 小的 dp 组合都加入里面。

代码：

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n, m;
    while (cin >> n >> m) {
        vector<int> dp(n + 1, 0);
        dp[0] = 1;
        for (int i = 1; i <= n; i++) { // 遍历背包
            for (int j = 1; j <= m; j++) { // 遍历物品
                if (i - j >= 0) dp[i] += dp[i - j];
            }
        }
        cout << dp[n] << endl;
    }
}