代码随想录算法训练营DAY46|C++动态规划Part8|139.单词拆分、多重背包理论基础、背包问题总结篇

文章目录

139.单词拆分
- 思路
- CPP代码
多重背包理论基础
- 处理输入
- 把所有个数大于1的物品展开成1个
- 开始迭代，计算dp数组
- 代码优化
背包问题总结篇

139.单词拆分

力扣题目链接

文章讲解：139.单词拆分

视频讲解：你的背包如何装满？| LeetCode：139.单词拆分
状态：本题主要还是两个地方要注意：一个是s.substr的使用，另外一个就是遍历顺序，最后是对内循环循环终止条件的考量.

本题其实是可以使用回溯算法来写的，具体可以直接去看卡哥的文章：回溯算法和优化思路

如果使用动态规划应该怎么写呢？

题目中要求我们用wordDict中的元素，看能不能组合成字符串s，其实已经很直观了！

也就是说我们的物品是wordDict，背包容量是s，看这些物品能不能正好装满这个背包。同时，题目中说了我们的物品元素是能够使用多次的，所以本题是一道很奈斯的完全背包问题！

思路

dp数组含义

如果这个字符串长度为i，如果能被wordDict的单词组成的话，那么dp[i]=true，最终的结果其实就是dp[s.size]到底是true还是false（我们用dp[0]来表示空字符串的状态）

递推公式

这个递推公式其实蛮复杂的该说不说。这里数形结合进行表示

如果我们的dp[j]为true，并且我们的N子段为wordDict中的元素，那就可以完美推导出dp[i]也为true

if (wordSet.find(N) != wordSet.end() && dp[j]==true)
  	dp[i]=true

初始化
这里的初始化很重要，dp[0]必须初始化成true，如果dp[0]初始化成false的话对导致后面的推导全部是false（因为我们仍然要借助前面的dp[j]来判断后面的dp[i]）。然后非零下标为了不影响赋值所以都初始化成false
遍历顺序

对于完全背包问题，两层for循环的讨论非常有必要，这里再次做总结

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

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

求组合数的题有：518.零钱兑换II

求排列数的题有：377. 组合总和 Ⅳ 、70. 爬楼梯进阶版（完全背包）

求最小数的题有：322. 零钱兑换、279.完全平方数

在本题中，我们求的很明显是排列数，也就是说关注顺序，比如说s = “applepenapple”, wordDict = [“apple”, “pen”]

“apple”, “pen” 是物品，那么我们要求物品的组合一定是 “apple” + “pen” + “apple” 才能组成 “applepenapple”。

“apple” + “apple” + “pen” 或者 “pen” + “apple” + “apple” 是不可以的，那么我们就是强调物品之间顺序。

所以本题一定是先遍历背包，再遍历物品。

打印

以输入: s = “leetcode”, wordDict = [“leet”, “code”]为例，dp状态如图：

CPP代码

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
        vector<bool> dp(s.size() + 1, false);
        dp[0] = true;
        for (int i = 1; i <= s.size(); i++) {   // 遍历背包
            for (int j = 0; j < i; j++) {       // 遍历物品
                string word = s.substr(j, i - j); //substr(起始位置，截取的个数)
                if (wordSet.find(word) != wordSet.end() && dp[j]) {
                    dp[i] = true;
                }
            }
        }
        return dp[s.size()];
    }
};

时间复杂度：O(n^3)，因为substr返回子串的副本是O(n)的复杂度（这里的n是substring的长度）
空间复杂度：O(n)

多重背包理论基础

卡码网第56题

文章讲解：多重背包理论基础

什么叫多重背包问题呢？其实就是在01背包的基础上多了一个物品数量的维度。

	重量	价值	数量
物品0	1	15	2
物品1	3	20	3
物品2	4	30	2

可以转换成01背包问题吗？必须的

	重量	价值	数量
物品0	1	15	1
物品0	1	15	1
物品1	3	20	1
物品1	3	20	1
物品1	3	20	1
物品2	4	30	1
物品2	4	30	1

处理输入

题目中谈到，“宇航舱最大容量为C”，即背包的最大容量为C；
“有N种不同的矿石”，表示物品的种类有N个；
每种矿石有一个重量w[i]，一个价值v[i]，以及最多k[i]个可用，这段描述可以确定是典型的多重背包问题。输入形式如下：

输入共包括四行，第一行包含两个整数 C 和 N，分别表示宇航舱的容量和矿石的种类数量。
接下来的三行，每行包含 N 个正整数。具体如下：
第二行包含 N 个整数，表示 N 种矿石的重量。
第三行包含 N 个整数，表示 N 种矿石的价格。
第四行包含 N 个整数，表示 N 种矿石的可用数量上限。

int bagWeight, n;
cin >> bagWeight >> n;
vector<int> weight(n, 0);
vector<int> value(n, 0);
vector<int> nums(n, 0);
for (int i = 0; i < n; i++) cin >> weight[i];
for (int i = 0; i < n; i++) cin >> weight[i];
for (int i = 0; i < n; i++) cin >> weight[i];

把所有个数大于1的物品展开成1个

展开的过程不在乎顺序，直接往对应数组后面插即可

for (int i = 0; i < n; i++) {
	while (nums[i] > 1) { //物品数量不是一的，都展开
		weight.push_back(weight[i]);
		value.push_back(value[i]);
		nums[i]--
	}
}

开始迭代，计算dp数组

完全按照01背包的搞法来整

vector<int> dp(bagWeight + 1, 0);
for (int i = 0; i < weight.size(); i++) {
	for (int j = bagWeight; j >= weight[i]; j--) {
		dp[j] = max(dp[j], dp[j - weight[i]] + value[i];
	}
	cout << dp[bagWeight] << endl;
}

代码优化

如果提交刚刚那段代码，我们会发现代码超时了！
我们再来审视一下之前的代码，其实出问题的就在于vector底层的动态扩容，虽然根据扩容操作的平摊事件时间复杂度，vector底层的动态扩容应该是O(1)，但是数据量较大的时候还是会遇到插入延迟，所以我们应该对其进行优化。

for (int i = 0; i < n; i++) {
    while (nums[i] > 1) { // 物品数量不是一的，都展开
        weight.push_back(weight[i]);
        value.push_back(value[i]);
        nums[i]--;
    }
}

我们可以先把所有物品数量都计算好，然后一起申请vector的空间。

    //方法：reserve
    // 计算总共需要的空间
    int totalItems = 0;
    for (int i = 0; i < n; i++) {
        totalItems += nums[i];
    }

    vector<int> expandedWeight;
    vector<int> expandedValue;
    expandedWeight.reserve(totalItems); // 预分配足够的空间
    expandedValue.reserve(totalItems);

    // 填充物品
    for (int i = 0; i < n; i++) {
        for (int count = 0; count < nums[i]; count++) {
            expandedWeight.push_back(weight[i]);
            expandedValue.push_back(value[i]);
        }
    }

	//方法二：resize
	// 计算总共需要的空间
    int totalItems = 0;
    for (int i = 0; i < n; i++) {
        totalItems += nums[i];
    }

    // 使用 resize 预设大小，并在原数组上操作
    weight.resize(totalItems);
    value.resize(totalItems);

    int index = n; // 从原始数组大小开始填充新元素
    for (int i = 0; i < n; i++) {
        for (int count = 1; count < nums[i]; count++) { // 已有一个初始元素，所以从1开始
            weight[index] = weight[i];
            value[index] = value[i];
            index++;
        }
    }

再就是把每种商品遍历的个数放在01背包里面一起遍历

//最终代码
#include<iostream>
#include<vector>
using namespace std;
int main() {
    int bagWeight,n;
    cin >> bagWeight >> n;
    vector<int> weight(n, 0);
    vector<int> value(n, 0);
    vector<int> nums(n, 0);
    for (int i = 0; i < n; i++) cin >> weight[i];
    for (int i = 0; i < n; i++) cin >> value[i];
    for (int i = 0; i < n; i++) cin >> nums[i];

    vector<int> dp(bagWeight + 1, 0);

    for(int i = 0; i < n; i++) { // 遍历物品
        for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
            // 以上为01背包，然后加一个遍历个数
            for (int k = 1; k <= nums[i] && (j - k * weight[i]) >= 0; k++) { // 遍历个数
                dp[j] = max(dp[j], dp[j - k * weight[i]] + k * value[i]);
            }
        }
    }

    cout << dp[bagWeight] << endl;
}