【C++编程能力提升】

一、完全背包问题

1、完全背包与01背包的区别

第一，物品的有限与无限；
01背包：物品是有限的。（每个物品只能被选择一次放入背包）
完全背包：物品是无限的；（即可以重复选择某物品装入背包）

第二，遍历顺序存在不同；
01背包遍历背包容量时是从大到小的倒序遍历，目的是保证每个物品仅被添加一次；
完全背包添加物品是可以是多次，因此需要从小到大遍历，即按背包容量顺序遍历；

第三，遍历物品和背包容量的先后顺序。
01背包使用一维dp数组时必须要求先遍历物品再遍历背包容量（二维dp数组的遍历顺序没有要求）；
完全背包使用一维dp数组的遍历顺序是没有要求的，但是这仅仅对于纯完全背包问题，在某些具体问题上遍历顺序是有要求的。

二、518 零钱兑换II

题目链接：518 零钱兑换II

核心：硬币（物品）有无限个，且背包最大容量是amount，可以建模成完全背包问题。
dp[j]：装满背包容量j时的不同方法数，可知求解的是组合数，即递推公式是累加。
注意：组合问题先遍历物品，再遍历背包容量（因为无排列顺序要求，保证不同顺序的组合只计数一次）；排列问题先遍历背包容量，再遍历物品，因为排列存在顺序要求，即不同顺序的排列都需要计数。

    int change(int amount, vector<int>& coins) {
    //完全背包问题，且给定背包容量amount求解组合方法数（累加）
        vector<int> dp(amount+1,0);
        dp[0]=1;    //初始化必须为1
        for(int i=0;i<coins.size();++i)
        {//组合问题先遍历物品（即硬币值），再遍历背包容量j
            for(int j=coins[i];j<=amount;++j)
                dp[j]+=dp[j-coins[i]];  //组合需要累加
        }
        return dp[amount];
    }
1
2
3
4
5
6
7
8
9
10
11

三、377 组合总和IV

题目链接：377 组合总和IV

核心：给定背包容量target，数组元素可以使用无限次，故可以建模成完全背包问题。
由于不同顺序的组合属于不同的组合个数，即考虑排列顺序问题，因此实质是求解排列。
排列问题：先遍历背包容量，再遍历物品。

    int combinationSum4(vector<int>& nums, int target) {
    //完全背包问题，且给定背包容量target求解不同方法数，表面看似组合，实际却是排列
        vector<int> dp(target+1,0); //dp[j]:装满容量j的背包的不同方法数
        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];
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14