代码随行算法训练营第 46 天 | Leetcode 139. 分词，cardcode.com 56.携带矿石资源（含基本解决方案和多背包优化方案）

文章目录

• • Leetcode 139.单词拆分
  • 卡码网 56. 携带矿石资源
  • • 方法一： 分组转化成01背包
    • 方法二： 转化成01背包+完全背包（基于方法一的小优化）
    • 方法三： 二进制优化（优化了方法一的分组方式）

Leetcode 139.单词拆分

题目链接：Leetcode 139.单词拆分
题目描述： 给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
思路： 由于单词可以重复使用，并且要求正确顺序，因此可以联想到完全背包中的求排列问题。

• dp[i] : 字符串长度为i的话，dp[i]为true，表示可以拆分为一个或多个在字典中出现的单词。
• 递推公式：如果截取的单词[i - sz, sz]等于word并且dp[i - sz] == true,则dp[i] = true
• 初始化：dp[0] = ture
• 遍历顺序：先遍历背包，后遍历物品。

代码如下：

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        vector<bool> dp(s.size() + 5);
        dp[0] = true;
        // 完全背包求排列问题
        for (int i = 1; i <= s.size(); i++) // 先遍历背包
            for (auto& word : wordDict) {   // 后遍历物品
                int sz = word.size();
                // 首先背包容量要大于单词大小
                // 其次，如果截取的单词[i-sz,sz]等于word并且dp[i-sz]==true,则dp[i]=true
                if (i >= sz && s.substr(i - sz, sz) == word) {
                    dp[i] = dp[i] || dp[i - sz];
                }
            }
        return dp[s.size()];
    }
};

• 时间复杂度$O(n^2)$
• 空间复杂度$O(n)$

卡码网 56. 携带矿石资源

题目链接：卡码网 56. 携带矿石资源

思路： 这道题是多重背包的模板题。首先观察多重背包的特点是每件物品的数量不相同，其余的条件和01背包和完全背包很像，那能不能将其转化成它们呢？答案是可以。

方法一： 分组转化成01背包

由于多重背包每件物品数量不相同，不知道一种占用空间 w ，价值为 v，数量为 s 的物品该拿多少件，因此我们就把该拿多少件枚举一下，假设为 k件1 <= k <= s ，然后我们就把问题看成仅有一件的占用空间k * w ，价值为k * v的物品该不该拿。
代码如下：

#include <iostream>
#include <vector>
 
using namespace std;
 
const int N = 1e4 + 5;
 
int w[N],v[N],k[N];
int dp[N];
int n,m;
 
int main()
{
    cin >> n >> m;//背包大小和物品数量
    for(int i = 1; i <= m; i ++ ) cin >> w[i];
    for(int i = 1; i <= m; i ++ ) cin >> v[i];
    for(int i = 1; i <= m; i ++ ) cin >> k[i];
    //转化成01背包
    for(int i = 1; i <= m; i ++ )//遍历物品
        for(int j = n; j >= w[i]; j -- )//遍历背包
            //遍历个数
            for(int num = 1; num <= k[i] && j - num * w[i] >= 0; num ++ )
                dp[j] = max(dp[j], dp[j - num * w[i]] + num * v[i]);
                 
    cout << dp[n];
    return 0;
}

• 时间复杂度$O(n^3)$
• 空间复杂度$O(n)$

方法二： 转化成01背包+完全背包（基于方法一的小优化）

我们发现，如果k个物品的总重量大于等于背包的最大容量，说明在当前大小的背包容量下，该物品有无限个和只有k个的效果是相同的，这部分物品就转化成了完全背包问题。

为什么要转换成完全背包？我们看方法一转化成01背包是需要枚举一下拿多少件的，而转化为完全背包是不需要枚举多少件的，可以拿我们就拿，所以在时间上会有一些优化。（尽管时间复杂度不变）

代码如下：

#include <iostream>
#include <vector>
 
using namespace std;
 
const int N = 1e4 + 5;
 
int w[N],v[N],k[N];
int dp[N];
int n,m;
 
int main()
{               
    cin >> n >> m;//背包大小和物品数量
    for(int i = 1; i <= m; i ++ ) cin >> w[i];
    for(int i = 1; i <= m; i ++ ) cin >> v[i];
    for(int i = 1; i <= m; i ++ ) cin >> k[i];
    //转化成01背包+完全背包
    for(int i = 1; i <= m; i ++ )//遍历物品
    {
        if(k[i] * w[i] >= n)//如果不能把某个物品全部一次性装下，则可转化为完全背包
        {
            for(int j = w[i]; j <= n; j ++ )
                dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
                 
        }else
        {
            for(int j = n; j >= w[i]; j -- )//遍历背包
                //遍历个数
                for(int num = 1; num <= k[i] && j - num * w[i] >= 0; num ++ )
                    dp[j] = max(dp[j], dp[j - num * w[i]] + num * v[i]);
                 
        }
         
    }
                 
    cout << dp[n];
    return 0;
}

• 时间复杂度$O(n^3)$
• 空间复杂度$O(n)$

方法三： 二进制优化（优化了方法一的分组方式）

我们发现利用从$1$ 、$2$、$4$…… $2^n$可以枚举出$[0,2^n-1]$的所有数字（利用等比数列求和可以证明），因此可以不用像方法一那样依次枚举每个数字，本题数据范围是$10^4$，而$2^{13}=8192$，也就是每个数字最多分为$14$组即可，不必依次枚举k，大大降低了时间复杂度。
代码如下：

#include <iostream>
#include <vector>

using namespace std;

const int N = 1e4 + 5;
const int M = 13 * N + 5;//根据数据范围，一个数最多拆13次，因此要比原来多开一些空间
int w[N],v[N],k[N];
int W[M],V[M];//用来记录分组之后的物品重量和价值
int dp[N];
int n,m;

int main()
{               
    cin >> n >> m;//背包大小和物品数量
    for(int i = 1; i <= m; i ++ ) cin >> w[i];
    for(int i = 1; i <= m; i ++ ) cin >> v[i];
    for(int i = 1; i <= m; i ++ ) cin >> k[i];
    //将物品数量按照（1，2，4...2^n）分组，然后转化为01背包（优化了遍历次数）
    int cnt = 0;//记录物品数量
    for(int i = 1; i <= m; i ++ )//分组过程
    {
        int num = 1;
        while(num <= k[i])
        {
            cnt ++ ;
            W[cnt] = num * w[i];
            V[cnt] = num * v[i];
            k[i] -= num;
            num *= 2;
        }
        if(k[i])//剩下的直接放入
        {
            cnt ++ ;
            W[cnt] = k[i] * w[i];
            V[cnt] = k[i] * v[i];
        }
    }
    //01背包过程
    for(int i = 1;i <= cnt; i ++ )
        for(int j = n; j >= W[i]; j -- ){
            dp[j] = max(dp[j], dp[j - W[i]] + V[i]);
        }
            
    //输出
    cout << dp[n];
    return 0;
}

• 时间复杂度$O(n^{2}logn)$
• 空间复杂度$O(n)$

---

总结： 遇到一个新问题首先我们可以思考是否可以利用已有知识来解决，就像多重背包的解法就是基于01背包和完全背包。

最后，如果文章有错误，请在评论区或私信指出，让我们共同进步！