代码随想录算法训练营第四十四天|139.单词拆分、56.携带矿石资源

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

139.单词拆分

思路：将字符串s看作为背包容量，从字符串中获取物品，刚好满足背包容量的过程，因为可以从字符串中多次取值，相当于物品的数量是不限制，这就是一个完全背包的问题！这个题有个关键点，在于遍历物品的时候，分为两部分，一部分是前j个部分，判断这部分是否是物品中的东西，另外一部分就是判断剩下这部分是否是物品中的东西，相当于把一个子串也要拆分！一个大的串，就是多个子串组成，并且这些子串还是有顺序的！

class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {unordered_set<string> myset(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);if(myset.find(word)!=myset.end()&&dp[j]==true){dp[i]=true;}}}return dp[s.size()];}
};

56.携带矿石资源

思路：将每个类型的数量进行展开，最后变成01背包问题，但是展开的时候，要区分，应该在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;
}