leetcode_day40

今日内容：

• 完全背包
• 518. 零钱兑换Ⅱ medium
• 377. 组合总和Ⅳ medium

完全背包

题目：

有\(N\)种物品和一个容量是\(V\)的背包，每种物品都有无限件可用。

第\(i\)种物品的体积是\(v_i\)，价值是\(w_i\)。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

输出最大价值。

输入格式：

第一行两个整数，\(N\)，\(V\)，用空格隔开，分别表示物品种数和背包容积。

接下来有\(N\)行，每行两个整数\(v_i\),\(w_i\)，用空格隔开，分别表示第\(i\)种物品的体积和价值。

输出格式:

输出一个整数，表示最大价值。

数据范围

\(0<N,V≤1000\)

\(0<v_i,w_i≤1000\)

思路：

相对于01背包，物品数量不受限制，可以多次放入，那么就要改动容量倒序遍历，容量倒序遍历原本目的是为了防止多次放入，但现在可以多次放入，不能防止，所以改为顺序遍历，其他不变。

代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    int N, V;
    cin >> N >> V;
    vector<int> v(N), w(N);
    for(int i = 0;i < N;i++) {
        cin >> v[i] >> w[i] ;
    }
    
    vector<int> dp(V + 1);
    for(int i = 0;i < N;i++) {
        for(int j = v[i];j <= V;j++) {
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
        }
    }
    cout << dp[V] << endl;
    return 0;
}

518. 零钱兑换Ⅱ

题目：

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

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

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

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

思路：

硬币无限+凑总金额，很容易看出使用完全背包。题目所求硬币组合数，和昨天的目标和很像，核心代码都是dp[j] += dp[j - nums[i]]，照着样子套就行。

carl强调：要注意遍历的顺序，首先完全背包遍历背包容量时要顺序遍历以实现多次拿取，其次要先遍历物品再遍历背包容量，不然就会求成排列数而非组合数：

• 先物品后容量 ==> 组合数
• 先容量后物品 ==> 排列数

可自推dp数组画图

代码

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        int N = coins.size();
        vector<int> dp(amount + 1, 0);
        dp[0] = 1;
        for(int i = 0;i < N;i++) {
            for(int j = coins[i];j <= amount;j++) {
                dp[j] += dp[j - coins[i]];
            }
        }
        return dp[amount];
    }
};

377. 组合总和Ⅳ

题目：

给你一个由不同 整数组成的数组 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)

请注意，顺序不同的序列被视作不同的组合。

思路：

有上一道题的经验，安排这题作为下一题非常合适，直接当场体会遍历顺序对结果的影响。

这道题所求组合个数，但却又在示例中说明顺序不同的序列视作不同组合，与通用概念存在矛盾。不过总之是求通用概念的排列数，先遍历容量再遍历物品即可。

代码

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