手机版网站公司的,网站做移动端,莱阳网站开发,杭州网站推广宣传文章目录 单词拆分思路#xff1a;代码 多重背包≈0-1背包题目代码 背包总结 单词拆分
3
思路#xff1a; 代码
class Solution {public boolean wordBreak(String s, ListString wordDict) {HashSetString set new HashSet(wordDict);boolean[]… 文章目录 单词拆分思路代码 多重背包≈0-1背包题目代码 背包总结 单词拆分
3
思路 代码
class Solution {public boolean wordBreak(String s, ListString wordDict) {HashSetString set new HashSet(wordDict);boolean[] dpnew boolean[s.length()1];dp[0]true;//先背包体积再物品for(int j1;js.length();j){for(int i0;ij;i){if(dp[i]trueset.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 scnew 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[] dpnew int[c1];for(int i0;in;i){for(int jc;jweight[i];j--){// 每个i物品的循环都考虑k个for(int k1;knumbers[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]);}}
}背包总结
代码随想录背包总结
