代码随想录算法训练营第51天 | 139.单词拆分 多重背包理论基础

单词拆分

这道题最后是判断能否组成，很像回溯法的问题形式，和分割回文串那道题比较类似，所以是可以用回溯法解决的，但是回溯法需要使用记忆化递归来避免超时。

class Solution{
public:bool backtracking(const string s, const unordered_set<string>& wordSet, vector<bool>& memory, int startIndex){if(startIndex == s.size()){return true;}// 如果当前位置的memory数组已经更新，直接用memory的结果，不必再一次计算if(!memory[startIndex])  return memory[startIndex];for(int i = startIndex; i < s.size(); i++) {string word = s.substr(startIndex, i - startIndex + 1);if(wordSet.find(word) != wordSet.end() && backtracking(s, wordSet, memory, i + 1)){return true;}}// startIndex位置开始的字符串无法由给定的字符串组成，记录下来memory[startIndex] = false;  return false;}bool wordBreak(string s, vector<string>& wordDict) {unordered_set<string> wordSet(wordDict.begin(), wordDict.end());vector<bool> memory(s.size(), 1);return backtracking(s, wordSet, memory, 0);}
};

动态规划方法

因为给定的字符串可以重复使用，所以是完全背包。
dp[i]：长度为 i 的字符串，如果可以被拆分成给定的那些字符串，那么dp[i] = true。
递推公式：遍历小于 i 的整数 j，如果dp[j] = true，说明在下标j - 1之前的字符串已经符合要求，同时再满足 [j, i) 的字符串可以在给定数组中找到，那么就可以给 dp[i] 赋值 true。
遍历顺序：匹配字符串是要限制顺序的，所以应该先背包后物品。

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++) {  // 由于涉及到字符串的索引，同时这里i是长度j是下标，循环结束的判断条件应该自己模拟一下再决定string word = s.substr(j, i - j);if(dp[j] && wordSet.find(word) != wordSet.end()){  // 两项都满足dp[i] = true;}}}return dp[s.size()];}
};

多重背包理论基础

多重背包物品的数目是有限个，我们在遍历的过程中就需要针对某物品考虑到底选几个的问题。方法就是将有多个的物品拆开，这样每一个物品又仅有一个了，多重背包就转化为了01背包。但是这样操作容易超时，可以将遍历物品数目的循环加入到dp数组递推中。

#include <bits/stdc++.h>
using namespace std;
int main() {int bagSize, n;while(cin >> bagSize >> 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(bagSize + 1, 0);for(int i = 0; i < n; i++) {for(int j = bagSize; j >= weight[i]; j--) {for(int k = 1; k <= nums[i] && k * weight[i] <= j; k++) {dp[j] = max(dp[j], dp[j - k * weight[i]] + k * value[i]);}}}cout << dp[bagSize] << endl;}
}