长沙找工作哪个网站好,新乡网站建设哪家好,大连网站建设制作公司,录播教育系统网站建设费用提示#xff1a;文章写完后#xff0c;目录可以自动生成#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、力扣139. 单词拆分二、力扣动态规划#xff1a;关于多重背包#xff0c;你该了解这些#xff01; 前言 提示#xff1a;以下是本篇文章正文内容#x… 提示文章写完后目录可以自动生成如何生成可参考右边的帮助文档 文章目录 前言一、力扣139. 单词拆分二、力扣动态规划关于多重背包你该了解这些 前言 提示以下是本篇文章正文内容下面案例可供参考
一、力扣139. 单词拆分
class Solution {public boolean wordBreak(String s, ListString wordDict) {HashSetString set new HashSet(wordDict);boolean[] dp new boolean[s.length()1];dp[0] true;for(int i 1; i s.length(); i ){for(int j 0; j i !dp[i]; j ){if(dp[j] set.contains(s.substring(j,i))){dp[i] true;}}}return dp[dp.length-1];}
}二、力扣动态规划关于多重背包你该了解这些
public void testMultiPack1(){// 版本一改变物品数量为01背包格式ListInteger weight new ArrayList(Arrays.asList(1, 3, 4));ListInteger value new ArrayList(Arrays.asList(15, 20, 30));ListInteger nums new ArrayList(Arrays.asList(2, 3, 2));int bagWeight 10;for (int i 0; i nums.size(); i) {while (nums.get(i) 1) { // 把物品展开为iweight.add(weight.get(i));value.add(value.get(i));nums.set(i, nums.get(i) - 1);}}int[] dp new int[bagWeight 1];for(int i 0; i weight.size(); i) { // 遍历物品for(int j bagWeight; j weight.get(i); j--) { // 遍历背包容量dp[j] Math.max(dp[j], dp[j - weight.get(i)] value.get(i));}System.out.println(Arrays.toString(dp));}
}public void testMultiPack2(){// 版本二改变遍历个数int[] weight new int[] {1, 3, 4};int[] value new int[] {15, 20, 30};int[] nums new int[] {2, 3, 2};int bagWeight 10;int[] dp new int[bagWeight 1];for(int i 0; i weight.length; 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] Math.max(dp[j], dp[j - k * weight[i]] k * value[i]);}System.out.println(Arrays.toString(dp));}}
}
