DAY42 ||完全背包理论 | 518. 零钱兑换 II | 377. 组合总和 Ⅳ|70. 爬楼梯 （进阶）

完全背包理论

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

完全背包和01背包问题唯一不同的地方就是，每种物品有无限件。

不同于01背包，二者的区别就是遍历顺序。完全背包的物品背包的内外层循环顺序不影响求值。这里是背包从小到大遍历。

以下是纯完全背包题目52. 携带研究材料（第七期模拟笔试） (kamacoder.com)

代码

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

void test_CompletePack(vector<int>weight,vector<int>value,int bagweight)
{
    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]);//不选择和选择比大小
    }//if那里是保证空背包装得下该物品
    
    cout<<dp[bagweight]<<endl;
}

int main()
{
    int N,V;
    cin>>N>>V;//研究物品的种类和行李空间
    
    vector<int>weight;
    vector<int>value;
    for(int i=0;i<N;i++)
    {
        int w,v;
        cin>>w>>v;//输入每个物品的重量和价值
        weight.push_back(w);
        value.push_back(v);
    }
    test_CompletePack(weight,value,V);
    return 0;
    
    
}

518.零钱兑换II

题目：518. 零钱兑换 II - 力扣（LeetCode）

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

假设每一种面额的硬币有无限个。 

题目数据保证结果符合 32 位带符号整数。

示例 1：

输入：amount = 5, coins = [1, 2, 5]
输出：4
解释：有四种方式可以凑成总金额：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

示例 2：

输入：amount = 3, coins = [2]
输出：0
解释：只用面额 2 的硬币不能凑成总金额 3 。

示例 3：

输入：amount = 10, coins = [10] 
输出：1

和纯完全背包不一样求满足背包的最大价值，本题求能凑成总金额（背包）的硬币的组合数。 

1.dp[j]：凑成总金额j的货币组合数为dp[j]

2.递推公式和494. 目标和 (opens new window)中就讲解了，求装满背包有几种方法，公式都是：dp[j] += dp[j - nums[i]];一样，都是只要加硬币进去个数就加一。

3.dp[0]初始化为1。

后台测试数据是默认，amount = 0 的情况，组合数为1的。

下标非0的dp[j]初始化为0，这样累计加dp[j - coins[i]]的时候才不会影响真正的dp[j]

dp[0]=1还说明了一种情况：如果正好选了coins[i]后，也就是j-coins[i] == 0的情况表示这个硬币刚好能选，此时dp[0]为1表示只选coins[i]存在这样的一种选法。

4.本题和纯完全背包不一样，一定先遍历物品再背包，所以这种遍历顺序中dp[j]里计算的是组合数！（防止（1，5）（5，1)重复出现

如果是两种都可以的是排列。

5.举例

代码 

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

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

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<uint64_t>dp(amount+1,0);
        dp[0]=1;//如果amount等于0，那么方式也只有一种

        for(int i=0;i<coins.size();i++)//遍历物品，因为求组合数
        {
            for(int j=coins[i];j<=amount;j++)
            dp[j]+=dp[j-coins[i]];//dp数组含义是装满容量为j的背包的硬币组合数
        }
        return dp[amount];

        
    }
};

为什么内层循环从 coins[i] 开始递增

• 避免重复计算：如果内层循环从 amount 开始递减，那么每个硬币只会被使用一次，这会导致我们计算的是排列数而不是组合数。例如，对于硬币 [1, 2] 和 amount = 3，递减循环会计算 [1, 1, 1] 和 [1, 2]，但不会计算 [2, 1]。
• 确保每个硬币可以被使用多次：递增循环确保每个硬币可以被使用多次，从而正确计算组合数

举例dp数组，看是不是特别简单。其实递增公式的意思和求目标和那题一样，就是不选当前物品的组合数（要达到某数总得累加到达上一步的方法数吧，这么看来和爬楼梯挺像的）加上选择了当前物品的组合数等于dp[j]。

1. 初始化 dp 数组：

   • dp = [1, 0, 0, 0, 0, 0]

2. 处理硬币 1：

   • dp[1] = dp[1] + dp[0] = 0 + 1 = 1
   • dp[2] = dp[2] + dp[1] = 0 + 1 = 1
   • dp[3] = dp[3] + dp[2] = 0 + 1 = 1
   • dp[4] = dp[4] + dp[3] = 0 + 1 = 1
   • dp[5] = dp[5] + dp[4] = 0 + 1 = 1
   • dp = [1, 1, 1, 1, 1, 1]

3. 处理硬币 2：

   • dp[2] = dp[2] + dp[0] = 1 + 1 = 2
   • dp[3] = dp[3] + dp[1] = 1 + 1 = 2
   • dp[4] = dp[4] + dp[2] = 1 + 2 = 3
   • dp[5] = dp[5] + dp[3] = 1 + 2 = 3
   • dp = [1, 1, 2, 2, 3, 3]

4. 处理硬币 5：

   • dp[5] = dp[5] + dp[0] = 3 + 1 = 4
   • dp = [1, 1, 2, 2, 3, 4]

377.组合总和Ⅳ 

题目·：377. 组合总和 Ⅳ - 力扣（LeetCode）

给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

题目数据保证答案符合 32 位整数范围。

示例 1：

输入：nums = [1,2,3], target = 4
输出：7
解释：
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意，顺序不同的序列被视作不同的组合。（这不就是求排列嘛。。。）

示例 2：

输入：nums = [9], target = 3
输出：0

提示：

• 1 <= nums.length <= 200
• 1 <= nums[i] <= 1000
• nums 中的所有元素 互不相同
• 1 <= target <= 1000

 思路

首先元素可以用无限次，那么本题就是完全背包。本题就是求排列数嘛！！和上题解题思路挺像的，就是遍历顺序换一下就行，先遍历背包再物品！！！dp[j]就代表求到target的方法数，初始化dp[0]=1（考虑到物品为0）。

代码

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++)
            {
                //如果 dp[j] 加上 dp[j - nums[i]] 之后超过了 INT_MAX，那么这个累加操作就会导致整数溢出，从而得到错误的结果。
                if(j>=nums[i]&&dp[j] < INT_MAX - dp[j - nums[i]])//保证背包装得进物品
                 dp[j]+=dp[j-nums[i]];
            }
           
        }
        return dp[target];
        
    }
};

 57.爬楼梯（进阶版）

题目：57. 爬楼梯（第八期模拟笔试） (kamacoder.com)

题目描述

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 

每次你可以爬至多m (1 <= m < n)个台阶。你有多少种不同的方法可以爬到楼顶呢？ 

注意：给定 n 是一个正整数。

输入描述

输入共一行，包含两个正整数，分别表示n, m

输出描述

输出一个整数，表示爬到楼顶的方法数。

输入示例：3 2

输出示例：3

提示：

当 m = 2，n = 3 时，n = 3 这表示一共有三个台阶，m = 2 代表你每次可以爬一个台阶或者两个台阶。

此时你有三种方法可以爬到楼顶。

• 1 阶 + 1 阶 + 1 阶段
• 1 阶 + 2 阶
• 2 阶 + 1 阶

 求排列数。

这次改为：一步一个台阶，两个台阶，三个台阶，.......，直到 m个台阶。问有多少种不同的方法可以爬到楼顶呢？

1阶，2阶，.... m阶就是物品，楼顶就是背包。每一阶可以重复使用。问跳到楼顶有几种方法其实就是问装满背包有几种方法。

此时大家应该发现这就是一个完全背包问题了！和上一题一样嘛。。。

dp[i]表示达到i（楼顶）的方法有多少种，这不就是变相的累加求和嘛。物品是能跳1，2，...阶。

初始dp[0]=1,一样的。遍历顺序是先背包后物品。

举例如上图。

代码

#include<iostream>
#include<vector>
using namespace std;
int main()
{
    int n,m;
    while(cin>>n>>m)
    {
        vector<int>dp(n+1,0);
        dp[0]=1;
        
        for(int i=1;i<=n;i++)//背包，从1开始，因为第一个已经初始化了
        {
            for(int j=1;j<=m;j++)//物品
            {
                if(i>=j)dp[i]+=dp[i-j];
            }
        }
         cout<<dp[n]<<endl;
    }
    return 0;
}