代码随想录算法训练营第四十六天|139.单词拆分，多重背包，背包问题总结

本文主要是介绍代码随想录算法训练营第四十六天|139.单词拆分，多重背包，背包问题总结，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

139.单词拆分

题目链接：704. 二分查找

文档讲解：代码随想录

视频讲解：动态规划之完全背包，你的背包如何装满？| LeetCode：139.单词拆分

思路

dp数组dp[i]表示长度为i的字符串是否可以拆分为一个或多个再字典中出现的单词。

递推公式：如果dp[j]为true，且[j, i]区间的字串出现在字典中，则dp[i]为true。

如：对于dp[i]，遍历j=0~i，如果字串[j, i]出现在字典中，且dp[j]为true，则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 = 0; i <= s.size(); i++) {for (int j = 0; j <= i; j++) {string word = s.substr(j, i - j);if (wordSet.find(word) != wordSet.end() && dp[j])dp[i] = true;}}return dp[s.size()];}
};

多重背包

题目链接：56. 携带矿石资源（第八期模拟笔试）

文档讲解：代码随想录

思路

将多重背包中的所有物品展开，则转换为01背包问题。

代码

#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>using namespace std;int main() {int C, N;cin >> C >> N;vector<int> weights(N, 0);vector<int> values(N, 0);vector<int> nums(N, 0);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 >> nums[i];int num_count = 0;for (auto i : nums)num_count += i;vector<int> stones_weights(num_count, 0);vector<int> stones_values(num_count, 0);int index = 0;for (int i = 0; i < N; i++) {for (int j = 0; j < nums[i]; j++) {stones_weights[index] = weights[i];stones_values[index] = values[i];index++;}}vector<int> dp(C + 1, 0);for (int i = 0; i < stones_weights.size(); i++) {for (int j = C; j >= stones_weights[i]; j--) {dp[j] = max(dp[j], dp[j - stones_weights[i]] + stones_values[i]);}}cout << dp[C] << endl;
}

背包问题总结

文档讲解：代码随想录

按背包类型分类：01背包、完全背包、多重背包等。

01背包：遍历背包时从后向前遍历
完全背包：遍历背包时从前向后遍历
多重背包：将物品展开转换为01背包问题

按所求问题分类：能否装满背包，背包最多装多少，装满背包有多少种方法，背包装满最大价值，装满背包所需最小物品数。

能否装满背包：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])，即01背包问题中价值和重量相同，装完背包后，最大价值与背包容量相同则可以装满背包。
背包最多装多少：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])，即01背包问题中价值和重量相同。
装满背包有多少种方法：dp[j] += dp[j - nums[i]]。
背包装满最大价值：dp[j] = max(dp[j], dp[j - weight[i]] + value[i])。
装满背包所需最小物品数：dp[j] = min(dp[j], dp[j - nums[i]] + 1)。

遍历顺序