本文主要是介绍代码随想录训练营Day 49|力扣139.单词拆分、关于多重背包，你该了解这些！、背包问题总结篇！，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1.单词拆分
视频讲解：动态规划之完全背包，你的背包如何装满？| LeetCode：139.单词拆分_哔哩哔哩_bilibili
代码随想录
代码：
class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {unordered_set<string> wordSet(wordDict.begin(),wordDict.end());// dp数组定义及初始化 dp[j]表示字符串下标从0~j的字符串是否能被所给的单词组成vector<bool> dp(s.size() + 1,false);dp[0] = true;// 递推公式3for(int j = 1; j <= s.size(); j++){for(int i = 0; i < j; i++){// 当dp[i]已经为真，j - i这段长度也为一个单词时，说明dp[j]为真string word = s.substr(i,j - i);if(wordSet.find(word) != wordSet.end() && dp[i]){dp[j] = true;}}}return dp[s.size()];}
};思路：
dp数组的含义：dp[j]表示字符串下标从0~j的字符串是否能被所给的单词组成
dp数组的递推公式：当dp[i]已经为真，j - i这段长度也为一个单词时，说明dp[j]为真。即为
if(wordSet.find(word) != wordSet.end() && dp[i] ){dp[j] = true;
}dp数组的初始化：为了让后面的值都有效，dp[0] = true
dp数组的遍历顺序：这道题不同的单词顺序不同会拼成不同的字符串，因此这是在求排列数。所以要先遍历背包，再遍历物品。
细节：这道题“物品”的处理方式和之前的不一样。我们是把 j - i 看成我们在dp[i]的基础上增加的新的字符，并且判断这个“物品”是不是题上给的单词序列里的。所以，这里的i必须小于j。
2.多重背包
代码随想录
代码：
#include <iostream>
#include <vector>
using namespace std;
int main(){int begweight,n;cin >> begweight >> 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];}// 定义dp数组及初始化vector<int> dp(begweight + 1,0);// 递推公式2for(int i = 0;i < n; i++){ // 遍历物品for(int j = begweight; 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[begweight] << endl;
}思路：
多重背包其实可以把物品摊开来看，这样就转换成了01背包。在01背包的基础上，再加一个循环来改变数量k的值，就好了。
这篇关于代码随想录训练营Day 49|力扣139.单词拆分、关于多重背包，你该了解这些！、背包问题总结篇！的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
