【Day33 LeetCode】动态规划DP Ⅵ 背包问题

一、动态规划DP Ⅵ 背包问题

1、leetcode.cn/problems/coin-change/description/" rel="nofollow">零钱兑换 322

本质是完全背包问题，以最终的金额数amount为背包容量，不同面额的硬币为物品，物品数量无数，求装满物品需要的最少物品数。直接套用完全背包模板。由于求最少物品数是在装满物品的方法里寻找，那么是寻找装满物品的组合还是排列呢？组合，因为最少物品数与顺序无关，所以采用组合即可。其实采用排列也是可以的，因为都是在结果里找到最少物品数，只是排列的结果范围更多。
下面是组合的代码：先遍历物品，再遍历背包

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, amount + 1);
        dp[0] = 0;
        for(int coin : coins)  // 先遍历物品
            for(int i=coin; i<=amount; ++i) // 再遍历背包
                dp[i] = min(dp[i], dp[i-coin] + 1);
        return dp[amount] < amount + 1 ? dp[amount] : -1;
    }
};

下面是排列的代码：先遍历背包，再遍历物品

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount+1, amount+1);
        dp[0] = 0;
        for(int i=1; i<=amount; ++i)
            for(int coin : coins)
                if(i>=coin)
                    dp[i] = min(dp[i], dp[i-coin]+1);
        return dp[amount] < amount+1 ? dp[amount] : -1;
    }
};

2、leetcode.cn/problems/perfect-squares/description/" rel="nofollow">完全平方数 279

这题与上一题零钱兑换几乎一模一样，只不过物品这里没写明，物品变成了平方小于等于背包容量的数，代码与上面几乎一模一样。
先遍历物品，再遍历背包，代码如下：

class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n + 1, n);
        dp[0] = 0;
        for(int i=1; i*i<=n; ++i)  // 先遍历物品
            for(int j=i*i; j<=n; ++j)  // 再遍历背包
                dp[j] = min(dp[j], dp[j-i*i]+1);
        return dp[n];
    }
};

先遍历背包，再遍历物品，代码如下：

class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n + 1, n);
        dp[0] = 0;
        for(int i=1; i<=n; ++i)  // 先遍历背包
            for(int j=1; j*j<=n; ++j)  // 再遍历物品
                if(i - j * j >= 0)
                    dp[i] = min(dp[i], dp[i-j*j]+1);
        return dp[n];
    }
};

3、leetcode.cn/problems/word-break/description/" rel="nofollow">单词拆分 139

目标字符串需要由字典里的子字符串构成，相当于使用物品为字典里的字符串，且没有数量限制，装满容量为目标字符串长度的背包的方法有多少个，这是个完全背包问题。并且，对于结果来说，子字符串的结果讲究顺序，需要遍历所有顺序，所以先遍历背包，再遍历物品。代码如下：

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> wordSet;
        for(string word : wordDict)
            wordSet.insert(word);
        int n = s.size();
        vector<int> dp(n + 1);
        dp[0] = 1;
        for(int i=1; i<=n; ++i)  // 先遍历背包
            for(string word : wordSet)  // 再遍历物品
                if(i >= word.size() && s.substr(i-word.size(), word.size())==word)
                    dp[i] |=  dp[i-word.size()];
        return dp[n];
    }
};

4、多重背包问题

将每个同一种类的物品视为一个独立的物品，那么就将多重背包问题转换成了01背包问题，这样做想法简单直接，但是在扩容vector时比较耗时。
另一种代码实现更高效的方法时在循环里使用不同数量的物品。

# include<iostream>
# include<vector>

using namespace std;

int main(){
    int Capacity, N;
    cin >> Capacity >> N; // 容量  物品种类数
    vector<int> weights(N), values(N), amount(N); // 重量、价值、数量
    for(int i=0; i<N; ++i)  cin >> weights[i];
    for(int i=0; i<N; ++i)  cin >> values[i];
    for(int i=0; i<N; ++i)  cin >> amount[i];
    
    vector<int> dp(Capacity+1);
    for(int i=0; i<N; ++i) // 遍历物品
        for(int j=Capacity; j>=weights[i]; --j)  // 遍历背包
            for(int kk=1; kk<=amount[i] && j - kk * weights[i] >= 0; ++kk)
                dp[j] = max(dp[j], dp[j - kk * weights[i]] + kk * values[i]);
    cout << dp[Capacity] << endl;
    return 0;
}