JLUVicent

完全背包理论基础&518零钱兑换II&377组合总和IV

 
  • 2023年 03月30日
  • 0 阅读

day44

完全背包理论基础

参考 视频

每个物品可以使用无限次

// 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-weigth[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]);
    }
}

同时物品和背包的遍历顺序是可以颠倒的，然而这是对于纯完全背包问题，具体问题需要具体确定遍历顺序

完全背包问题的二维dp数组实现：

// chatgpt生成结果
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m; // n表示物品数量，m表示背包容量

    // 初始化物品体积和价值
    vector<int> w(n + 1), v(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> w[i] >> v[i];
    }

    // 初始化DP数组
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));

    // 状态转移方程
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (j >= w[i]) {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - w[i]] + v[i]);
            }
            else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }

    // 输出最大价值
    cout << dp[n][m] << endl;

    return 0;
}

// 修改之前01背包的方法，需要改变初始化时候的值即可
for (int j = weight[0]; j <= bagweight; j++) {		//行初始化为对应的值
    dp[0][j] = values[0]*(j/weight[0]);	//二维背包第一行初始化和之前的不同
    //dp[0][j] = values[0];
}	//其余都相同

518.零钱兑换II

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

解题思路：参考 视频

完全背包：有背包和物品，每个物品可以被取无限次

凑成总金额的组合数而非排列数

动态规划五部曲：

1.确定dp[j]及下标的含义：凑成总金额为j的货币组合数为dp[j]

2.确定递推公式：dp[j] += dp[j-coins[i]]; 和目标和中的递归公式一样

求装满背包有几种方法的递推公式都是$dp[j] += dp[j-coins[i]]$

3.dp数组初始化：dp[0] = 1; 如果为0的话之后所有的推导就都为0了，其余都为0；

4.确定遍历顺序：

先遍历物品再遍历背包就是组合问题，先遍历背包再遍历物品就是排列问题

for( int i = 0; i < coins.size(); i++){ //遍历物品
    for( int j = coins[i]; j <= amount; j++){	//遍历背包
        dp[j] += dp[j - coins[i]];
    }
}
// for循环颠倒顺序就是排列数

5.打印dp数组

518.零钱兑换II

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

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

int main() {
    int amount,n;
    cout << "输入总金额和硬币数：";
    cin >> amount >> n;
    vector<int> coins(n);
    cout << "输入每个硬币的价值:";
    for (int i = 0; i < n; i++) cin >> coins[i];
    Solution solution;

    int test = solution.change(amount, coins);
    cout << "组合数为：";
    cout << test << endl;


    return 0;
}

如果求组合数就是外层for循环遍历物品，内层for遍历背包。

如果求排列数就是外层for遍历背包，内层for循环遍历物品。

377.组合总和IV

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

解题思路：参考 视频

这里的组合相当于排列问题，可以抽象为之前的爬楼梯的问题，所以在循环的时候需要考虑遍历顺序，先遍历背包再遍历物品。

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

求装满背包有几种方法，递归公式都是一样的，没有什么差别，但关键在于遍历顺序！

搜索