wordpress图站,兰州网络推广昔年下拉博客,wordpress 设置文章模板,网站开发核心技术JAVA代码编写
139.单词拆分
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
**注意#xff1a;**不要求字典中出现的单词全部都使用#xff0c;并且字典中的单词可以重复使用。
示例 1#xff1a;
输入: s **不要求字典中出现的单词全部都使用并且字典中的单词可以重复使用。
示例 1
输入: s leetcode, wordDict [leet, code]
输出: true
解释: 返回 true 因为 leetcode 可以由 leet 和 code 拼接成。示例 2
输入: s applepenapple, wordDict [apple, pen]
输出: true
解释: 返回 true 因为 applepenapple 可以由 apple pen apple 拼接成。注意你可以重复使用字典中的单词。示例 3
输入: s catsandog, wordDict [cats, dog, sand, and, cat]
输出: false教程https://programmercarl.com/0139.%E5%8D%95%E8%AF%8D%E6%8B%86%E5%88%86.html
方法一动态规划
思路单词就是物品字符串s就是背包单词能否组成字符串s就是问物品能不能把背包装满。
还是有点反应不过来。
拆分时可以重复使用字典中的单词说明就是一个完全背包
步骤 定义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[0] true其他初值都是false 确定遍历顺序: 如果求组合数就是外层for循环遍历物品内层for遍历背包。 如果求排列数就是外层for遍历背包内层for循环遍历物品。 强调物品之间顺序。 所以说本题一定是 先遍历背包再遍历物品。 举例推导dp数组 以输入: s “leetcode”, wordDict [“leet”, “code”]为例dp状态如图 复杂度分析
时间复杂度 O ( n 2 ) O(n^2) O(n2)空间复杂度 O ( m a x ( m , n ) ) O(max(m, n)) O(max(m,n))
class Solution {public boolean wordBreak(String s, ListString wordDict) {HashSetString set new HashSet(wordDict);boolean[] valid new boolean[s.length() 1];valid[0] true;for (int i 1; i s.length(); i) {for (int j 0; j i !valid[i]; j) {if (set.contains(s.substring(j, i)) valid[j]) {valid[i] true;}}}return valid[s.length()];}
}56. 携带矿石资源多重背包
题目描述
你是一名宇航员即将前往一个遥远的行星。在这个行星上有许多不同类型的矿石资源每种矿石都有不同的重要性和价值。你需要选择哪些矿石带回地球但你的宇航舱有一定的容量限制。
给定一个宇航舱最大容量为 C。现在有 N 种不同类型的矿石每种矿石有一个重量 w[i]一个价值 v[i]以及最多 k[i] 个可用。不同类型的矿石在地球上的市场价值不同。你需要计算如何在不超过宇航舱容量的情况下最大化你所能获取的总价值。
输入描述
输入共包括四行第一行包含两个整数 C 和 N分别表示宇航舱的容量和矿石的种类数量。
接下来的三行每行包含 N 个正整数。具体如下
第二行包含 N 个整数表示 N 种矿石的重量。
第三行包含 N 个整数表示 N 种矿石的价格。
第四行包含 N 个整数表示 N 种矿石的可用数量上限。
输出描述
输出一个整数代表获取的最大价值。
输入示例
10 3
1 3 4
15 20 30
2 3 2输出示例
90提示信息
数据范围
1 C 10000;
1 N 10000;
1 w[i], v[i], k[i] 10000;教程https://programmercarl.com/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80%E5%A4%9A%E9%87%8D%E8%83%8C%E5%8C%85.html#%E5%A4%9A%E9%87%8D%E8%83%8C%E5%8C%85
方法一动态规划
思路多重背包
有N种物品和一个容量为V 的背包。第i种物品最多有Mi件可用每件耗费的空间是Ci 价值是Wi 。求解将哪些物品装入背包可使这些物品的耗费的空间总和不超过背包容量且价值总和最大。
背包最大重量为10。
物品为
重量价值数量物品01152物品13203物品24302
每件物品是有限个
01背包和多重背包唯一不同就是物品的个数上我们直接针对遍历顺序经行分析
需要多加一个循环限制物品的数量
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] Math.max(dp[j], dp[j - k * weight[i]] k * value[i]);}}
}dp状态图如下 复杂度分析
时间复杂度 O ( n ∗ b a g W e i g h t 2 ) O(n * bagWeight^2) O(n∗bagWeight2)其中n是物品的数量bagWeight是背包的容量。空间复杂度O(bagWeight)其中bagWeight是背包的容量。
class Solution {public static void main(String[] args) {int bagWeight 10;int[] weight new int[] {1,3,4};int[] value new int[] {15,20,30};int[] nums new int[] {2,3,2};int n weight.length;int[] dp new int[bagWeight 1];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] Math.max(dp[j], dp[j - k * weight[i]] k * value[i]);}}}System.out.println(dp[bagWeight]);}
}
