單詞拆分

3

思路：

代碼

class Solution {public boolean wordBreak(String s, List<String> wordDict) {HashSet<String> set = new HashSet<>(wordDict);boolean[] dp=new boolean[s.length()+1];dp[0]=true;//先背包體積再物品for(int j=1;j<=s.length();j++){for(int i=0;i<j;i++){if(dp[i]==true&&set.contains(s.substring(i,j))){dp[j]=true;break;//快一點}}}return dp[s.length()];}
}

多重背包≈0-1背包

題目

代碼

import java.util.*;
public class Main{public static void main(String[] args){Scanner sc=new Scanner(System.in);// int while(sc.hasNextInt()){int c = sc.nextInt();int n = sc.nextInt();int[] weight = new int[n];int[] value = new int[n];int[] numbers = new int[n];for (int i = 0;i < n;i++) {weight[i] = sc.nextInt();}for (int i = 0;i < n;i++) {value[i] = sc.nextInt();}for (int i = 0;i < n;i++) {numbers[i] = sc.nextInt();}int[] dp=new int[c+1];for(int i=0;i<n;i++){for(int j=c;j>=weight[i];j--){// 每個i物品的循環都考慮k個for(int k=1;k<=numbers[i]&&(j-k*weight[i])>=0;k++){dp[j]=Math.max(dp[j],dp[j-k*weight[i]]+k*value[i]);}}}System.out.println(dp[c]);}}
}

背包總結

代碼隨想錄背包總結