当前位置：首页 > article >正文

C++ day44完全背包问题零钱兑换Ⅱ 组合总和Ⅳ

article 2024/9/21 0:40:27

完全背包：一个物品可以使用无数次，将01背包中倒序遍历背包变成正序遍历背包

遍历顺序：在完全背包中，对于一维dp数组来说，其实两个for循环嵌套顺序是无所谓的！

先遍历物品，后遍历背包可以；先遍历背包，后遍历物品也可以，因为dp[j] 是根据下标j之前所对应的dp[j]计算出来的，只要保证下标j之前的dp[j]都是经过计算的就可以了。

纯完全背包问题题目链接：完全背包

题目：有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。

代码1（先正序遍历物品，后正序遍历背包）

void full_backbag(vector<int>weight,vector<int> value,int bagweight){
    //初始化dp数组,定义dp数组
    vector<int> dp(bagweight+1,0);
    //递推。先正序遍历物品，后正序遍历背包
    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]);
        }
    }
    cout << dp[bagweight] << endl;
}

代码2（先正序遍历背包，后正序遍历物品）

void full_backbag(vector<int>weight,vector<int> value,int bagweight){
    //初始化dp数组,定义dp数组
    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]) dp[j]=max(dp[j],dp[j-weight[i]]+value[i]);
        }
    }
    cout << dp[bagweight] << endl;
}

又可以出一道面试题了，就是纯完全背包，要求先用二维dp数组实现，然后再用一维dp数组实现，最后再问，两个for循环的先后是否可以颠倒？为什么？

题目2：518 零钱兑换Ⅱ

题目链接：零钱兑换Ⅱ

对题目的理解

整数数组coins表示不同面额的硬币，整数amount表示总金额

返回可以凑成总金额的硬币组合有多少种，如果无法凑出，则返回0，假设每一种面额的硬币有无限个数据保证结果是带符号32位整数，注意求的是组合，不是排列

coins中至少有1个硬币，最多有300个硬币；硬币的面额至少是1，最大是5000，且记录的coins中的数值互不相同总金额在0~5000之间（闭区间）

每个物品可以使用无限次，是完全背包问题，但是本题和纯完全背包不一样，纯完全背包是凑成背包最大价值是多少，而本题是要求凑成总金额的物品组合个数！

动规五部曲

1）明确dp数组及下标的含义

dp[j]：装满容量为j的背包有dp[j]种方法，最终求解dp[amount]

2）递推公式

dp[j]+=dp[j-coins[i]]由目标和那道题得到

3）dp数组初始化

dp[0]=1 根据递推公式得到，如果dp[0] = 0 的话，后面所有推导出来的值都是0了。其他非零下标对应的dp[j]初始化为0，这样累加的时候才不会影响结果

4）遍历顺序（难点）

纯完全背包求得装满背包的最大价值是多少，和凑成总和的元素有没有顺序没关系，即：有顺序也行，没有顺序也行！能凑成总和就行

本题要求凑成总和的组合数，元素之间明确要求没有顺序，那么两个for循环就有顺序请求了

！！！先正序遍历物品，后正序遍历背包（组合）

这个是从前往后考虑每一个硬币，前面的硬币在之后不会重复，后面的硬币只在后面出现，所以没有重复的组合，所以这个是针对组合的，考虑容量的时候，后面只会考虑在前面硬币的基础上增加后面的硬币，而不会在后面的硬币不足的情况下，增加前面的硬币

！！！先正序遍历背包，后正序遍历物品（排列）

上述这个圈出来的3求解的时候，多计算了一次，因为前面计算coins[0]=1时，容量为3那个已经计算了{1，1，1}和{1，2}的组合，而下面在coins[1]=2，容量为3时，又计算了一次{2，1}的组合，所以这个是针对排列的

5）打印dp数组

代码

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        //定义并初始化dp数组
        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];
    }
};

时间复杂度: O(mn)，其中 m 是amount，n 是 coins 的长度
空间复杂度: O(m)

题目3：377 组合总和Ⅳ

题目链接：组合总和Ⅳ

对题目的理解

整数数组nums由不同整数组成，找出nums中总和为target的元素的组合个数（nums中的元素是可以重复使用的）但是本题求的是集合的个数，是一种排列（nums[i]>=1,nums数组中至少有一个元素）

本题元素可以重复使用，完全背包问题

如果本题要把排列都列出来的话，只能使用回溯算法爆搜。

动规五部曲

1）dp数组及下标的含义

总和为j的背包有dp[j]种排列最终求的是dp[target]

2) 递推公式

dp[j] += dp[j-nums[i]]

3）dp数组初始化

根据递推公式的累加，可推出dp[0]=1 ，不然，初始化为0的话，dp数组全为0；递推公式是累加的，所以其余非零下标的dp[j]均初始化为0，以免覆盖计算的dp结果

4）遍历顺序

由于题目要求的是排列，所以先遍历背包后遍历物品

5）打印dp数组

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        //定义并初始化dp数组
        vector<int> dp(target+1,0);
        dp[0] = 1;
        //递推，先正序遍历背包，后正序遍历物品，得到排列
        for(int j=0;j<=target;j++){
            for(int i=0;i<nums.size();i++){
                if(j>=nums[i] && dp[j]<INT_MAX-dp[j-nums[i]]) dp[j] += dp[j-nums[i]];
            }
        }
        return dp[target];
    }
};

时间复杂度: O(target * n)，其中 n 为 nums 的长度
空间复杂度: O(target)

！！！C++测试用例有两个数相加超过int的数据，所以需要在if里加上dp[i] < INT_MAX - dp[i - num],不然会报错！！！

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