完全背包

题目链接：52. 携带研究材料（第七期模拟笔试）

文档讲解：代码随想录

视频讲解：带你学透完全背包问题！ 和 01背包有什么差别？遍历顺序上有什么讲究？

思路

01背包的滚动数组解法中，遍历背包时从后向前遍历确保每个物品只使用一次，若从前向后遍历，则每个物品可以使用多次，称为完全背包。

代码

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int N, V;
    cin >> N >> V;
    vector<int> weights(N, 0);
    vector<int> values(N, 0);
    for (int i = 0; i < N; i++) {
        cin >> weights[i] >> values[i];
    }

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

    for (int i = 0; i < N; i++) {
        for (int j = weights[i]; j <= V; j++) {
            dp[j] = max(dp[j], dp[j - weights[i]] + values[i]);
        }
    }

    cout << dp[V];

    return 0;
}

518. 零钱兑换 II

题目链接：518. 零钱兑换 II

文档讲解：代码随想录

视频讲解：动态规划之完全背包，装满背包有多少种方法？组合与排列有讲究！| LeetCode：518.零钱兑换II

思路

每个硬币可以使用多次，为完全背包问题，不考虑硬币顺序，因此先遍历物品，再遍历背包

代码

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. 组合总和 Ⅳ

题目链接：377. 组合总和 Ⅳ

文档讲解：代码随想录

视频讲解：动态规划之完全背包，装满背包有几种方法？求排列数？| LeetCode：377.组合总和IV

思路

与上一题类似为完全背包问题，但是需要考虑每个数字的顺序，因此先遍历背包，再遍历物品。

代码

class Solution {
public:
    int combinationSum4(vector<int> &nums, int target) {
        vector<long long 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] && dp[i] + dp[i - nums[j]] < INT_MAX)
                    dp[i] += dp[i - nums[j]];
            }
        }

        return dp[target];
    }
};