算法训练营第四十六天|139.单词拆分 多重背包

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

Leetcode139.单词拆分

文章链接：代码随想录
题目链接：139.单词拆分

思路：完全背包，重点在于状态转移方程的条件。

class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {unordered_set wordS(wordDict.begin(), wordDict.end());vector<bool> dp(s.size() + 1, 0);dp[0] = true;for (int j = 1; j <= s.size(); j++){for(int i = 0; i < j; i++){string word = s.substr(i, j - i);if (wordS.find(word) != wordS.end() && dp[i]) dp[j] = true;}}return dp[s.size()];}
};

多重背包

文章链接：代码随想录
题目链接：卡码网：56. 携带矿石资源

思路：多重背包问题，将其拆解为01背包即可。

#include<bits/stdc++.h>
using namespace std;void solve(int C, int N){vector<int> dp(C + 1);vector<int> weight(N);vector<int> value(N);vector<int> nums(N);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];for (int i = 0; i < N; i++){for (int j = C; j >= weight[i]; j--){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[C] << endl;
}int main(){int C, N;cin >> C >> N;solve(C, N);return 0;
}

第四十六天打卡，这几天对做项目和学习路线有了新的理解和认识，重点不在看多少，在熟悉和掌握，加油！！！

这篇关于算法训练营第四十六天|139.单词拆分 多重背包的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---