代码随想录算法训练营day44

题目：完全背包、518. 零钱兑换 II、377. 组合总和 Ⅳ

参考链接：代码随想录

完全背包

思路：首先了解完全背包的定义，即每个物品的数量可以有无限个，即可以全部只放一个物品，01背包问题每一个物品只能放一个。同样dp五部曲：dp数组，dp[j]表示背包重量为j时能装的最大价值；递推公式，当物品i可以先放进去时，dp[j]=max(dp[j],dp[j-weight[i]]+value[i])；初始化，一开始都初始化为0；遍历顺序，这里就是完全背包和01背包的区别，01背包为了避免重复放入元素，会从背包容量从大到小的遍历，而完全背包问题每个元素可以重复放入，故从小到大遍历，因为我们就是要让物品可以重复放入！；举例：三个物品，weight={1,3,4}，value={15,20,30}，背包容量4，dp数组，初始化{0,0,0,0,0}，物品0，{0,15,30,45,60}，物品1，{0,15,30,45,60}，物品2，{0,15,30,45,60}。时间复杂度O(mn)

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

int solve(int n,int v,vector<int>& weight,vector<int>& value){
    vector<int> dp(v+1,0);
    for(int i=0;i<n;i++){
        for(int j=0;j<=v;j++){
            if(weight[i]<=j){
                dp[j]=max(dp[j],dp[j-weight[i]]+value[i]);
            }
        }
    }
    return dp[v];
}

int main(){
    int n,v;
    while(cin >> n >> v){
        vector<int> weight(n,0);
        vector<int> value(n,0);
        for(int i=0;i<n;i++){
            cin >> weight[i] >> value[i];
        }
        cout << solve(n,v,weight,value) << endl;
    }
    return 0;
}

本题有一个关键点，即遍历顺序，对于完全背包问题，使用一维数组，两个for循环先遍历物品后背包容量，和先背包容量后物品，都是可以的。因为dp[j]是根据j之前的dp[j]计算出来的，只要保证递推公式运行的时候之前的dp[j]已经被计算过即可。

518. 零钱兑换 II

思路：本题一个零钱可以无限使用，就是完全背包。背包重量为amount，物品weight为面值，value也为面值，需要保证背包恰好装满，求可以装满的方法数，故dp数组需要有所变化，回想目标和那题，但是不同之处是这里是组合数，而目标和那题是排列数！比如5=1+2+2和2+1+2是一种方法。dp五部曲：dp数组，dp[j]表示容量为j的背包装满用的方法数量（组合数）；递推公式，当物品i可以放入时，dp[j]+=dp[j-coins[i]]，这里就和之前比较类似了，所有求方法数基本都是这个递推公式；初始化，dp[0]一定初始化为1，即amount=0的组合数为1（一个钱都没有，也是一种方法），否则后面的所有递推都是0，然后是其他dp[j]初始化为0；遍历顺序，这里比较关键，普通的完全背包问题需要计算的是最大价值数，不管先遍历物品还是容量，最后算出来的答案都是一样的，但本题需要算的是组合方法数，如果先遍历物品后遍历容量，比如两个物品1和2，那么先放入的就是1，后放入的就是2，{1,2}，不会再算一遍{2,1}，故这样得到的答案就是正确的，如果先遍历容量后遍历物品，则每一个容量值，都计算了每一个物品的放入，包括{1,2}和{2,1}，这时算出来的是排列数，不符合要求；举例略。时间复杂度O(mn)。

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=0;j<=amount;j++){
                if(coins[i]<=j){
                    dp[j]+=dp[j-coins[i]];
                }
            }
        }
        return dp[amount];
    }
};

377. 组合总和 Ⅳ

思路：本题也是完全背包问题的思路，背包容量为target，weight和value都是nums中的元素，但是要求的是所有可能的组合数，不同顺序被视作不同的组合，故本题求的是排列数。需要注意，如果要求把所有结果列出，则只能使用回溯法暴搜，但本题只要求数量，故使用dp比较容易。dp五部曲：dp数组，dp[j]表示容量为j的背包装满的方法数量（排列数）；递推公式，如果物品i能先放进去，dp[j]+=dp[j-weight[i]]；初始化，dp[0]为1，其他为0；遍历顺序，这里比较关键，因为本题求的是排列数，和上题的组合数不同，需要把给定背包容量j下的所有情况都考虑一遍，故两个for循环先遍历容量后物品；举例略。时间复杂度O(mn)。

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

一开始提交出现runtime error，显示整数越界。看解答后发现需要保证答案在32位整数范围。
标答：

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