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;
}