最超值的赣州网站建设,淘宝代做网站,哈尔滨建筑专业网站,广西网络推广算法训练营 day50 动态规划 单词拆分 多重背包理论基础
单词拆分
139. 单词拆分 - 力扣#xff08;LeetCode#xff09;
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
注意#xff1a;不要求字典中出现的单词…算法训练营 day50 动态规划 单词拆分 多重背包理论基础
单词拆分
139. 单词拆分 - 力扣LeetCode
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
注意不要求字典中出现的单词全部都使用并且字典中的单词可以重复使用。
单词就是物品字符串s就是背包单词能否组成字符串s就是问物品能不能把背包装满。
拆分时可以重复使用字典中的单词说明就是一个完全背包 确定dp数组以及下标的含义 dp[i] : 字符串长度为i的话dp[i]为true表示可以拆分为一个或多个在字典中出现的单词。 确定递推公式 如果确定dp[j] 是true且 [j, i] 这个区间的子串出现在字典里那么dp[i]一定是true。j i 。 所以递推公式是 if([j, i] 这个区间的子串出现在字典里 dp[j]是true) 那么 dp[i] true。 dp数组如何初始化 从递推公式中可以看出dp[i] 的状态依靠 dp[j]是否为true那么dp[0]就是递推的根基dp[0]一定要为true否则递推下去后面都都是false了。 确定遍历顺序 题目中说是拆分为一个或多个在字典中出现的单词所以这是完全背包。 还要讨论两层for循环的前后顺序。 如果求组合数就是外层for循环遍历物品内层for遍历背包。 如果求排列数就是外层for遍历背包内层for循环遍历物品。 而本题其实我们求的是排列数为什么呢。 拿 s “applepenapple”, wordDict [“apple”, “pen”] 举例。“apple”, “pen” 是物品那么我们要求 物品的组合一定是 “apple” “pen” “apple” 才能组成 “applepenapple”。 “apple” “apple” “pen” 或者 “pen” “apple” “apple” 是不可以的那么我们就是强调物品之间顺序。所以说本题一定是 先遍历 背包再遍历物品。 举例推导dp[i] 以输入: s “leetcode”, wordDict [“leet”, “code”]为例dp状态如图 dp[s.size()]就是最终结果。
class Solution {public boolean wordBreak(String s, ListString wordDict) {boolean[] dp new boolean[s.length()1];Arrays.fill(dp,false);dp[0] true;HashSetString set new HashSet(wordDict);for (int i 1; i s.length(); i) {for (int j 0; j i; j) {if (set.contains(s.substring(j,i)) dp[j]){dp[i] true;}}}return dp[s.length()];}
}多重背包理论基础
有N种物品和一个容量为V 的背包。第i种物品最多有Mi件可用每件耗费的空间是Ci 价值是Wi 。求解将哪些物品装入背包可使这些物品的耗费的空间 总和不超过背包容量且价值总和最大。
多重背包和01背包是非常像的 为什么和01背包像呢
每件物品最多有Mi件可用把Mi件摊开其实就是一个01背包问题了。
例如
背包最大重量为10。
物品为
重量价值数量物品01152物品13203物品24302
问背包能背的物品最大价值是多少
和如下情况有区别么
重量价值数量物品01151物品01151物品13201物品13201物品13201物品24301物品24301
毫无区别这就转成了一个01背包问题了且每个物品只用一次。
改变物品数量为01背包格式
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));}}
}
