丹灶建网站,网站底部样式,论坛与网站做优化哪个更好,网站建设硬件环境一、单词拆分#xff08;完全背包#xff09; 1.1 题目 给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。 注意#xff1a;不要求字典中出现的单词全部都使用#xff0c;并且字典中的单词可以重复使用。
示例 1完全背包 1.1 题目 给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 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提示
1 s.length 3001 wordDict.length 10001 wordDict[i].length 20s 和 wordDict[i] 仅由小写英文字母组成wordDict 中的所有字符串 互不相同 1.2 题目链接 139.单词拆分 1.3 解题思路和过程想法 1解题思路 # 利用单词物体构成字典背包 # 数组字典 i 之前的所有部分是否能由单词构成 dp[i] # 初始化为在后续处理中便于被覆盖初始化其为 False dp [False] * (len(s) 1) # 初始化空格位置为 True ,不会影响后续元素的判断 dp[0] True # 递推关系若当前物体之前的位置为true且当前位置的单词存在于字典中 dp[j] dp[j] or (dp[j-len(word)] and word s[j-len(word):j]) 2过程想法 总体的思路很好理解但需构思递推关系怎么写 1.4 代码
class Solution:def wordBreak(self, s: str, wordDict: List[str]) - bool:# 利用单词物体构成字典背包# 数组字典 i 之前的所有部分是否能由单词构成 dp[i]# 初始化为在后续处理中便于被覆盖初始化其为 Falsedp [False] * (len(s) 1)# 初始化空格位置为 True ,不会影响后续元素的判断dp[0] True# 递推关系若当前物体之前的位置为true且当前位置的单词存在于字典中for j in range(1,len(s)1) : # 遍历背包for word in wordDict: # 遍历物体if j len(word):dp[j] dp[j] or (dp[j-len(word)] and word s[j-len(word):j]) return dp[len(s)]
二、携带矿石资源多重背包 1.1 题目
题目描述
你是一名宇航员即将前往一个遥远的行星。在这个行星上有许多不同类型的矿石资源每种矿石都有不同的重要性和价值。你需要选择哪些矿石带回地球但你的宇航舱有一定的容量限制。
给定一个宇航舱最大容量为 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; 1.2 题目链接 56.携带矿石资源 1.3 解题思路和过程想法 1解题思路 # 用矿石物品装满宇航仓背包因为每种物体的数量是有限但不都为1 属于多重背包问题处理思路在 0-1 背包的基础上加上数量判断。 # 数组宇航仓容量为 j 时其最大能获取的价值为 dp[j] # 初始化求最大且没有负值初始化为 0便于覆盖 dp [0] * (bagWeight 1) # 递推关系dp[j] max(dp[j], dp[j-weight[i]]value[i]) # 01背包问题——先遍历物体再遍历背包容量 2过程想法 卡哥说面试大多考 0-1 背包和完全背包问题这类多重背包问题参考看看即可 1.4 代码
def read_input():# 创建四个空列表用于存储四个数字列表values []weights []nums []for i in range(4):# 使用input函数获取用户输入line input(.format(i1))# 根据行号存储到相应的列表中if i 0:C, N map(int, line.strip().split())elif i 1:weights list(map(int, line.strip().split()))elif i 2:values list(map(int, line.strip().split()))elif i 3:nums list(map(int, line.strip().split()))return C, N, weights, values, numsdef maxValue(bagWeight,N,weights,values,nums):# 用矿石物品装满宇航仓背包# 数组宇航仓容量为 j 时其最大能获取的价值为 dp[j]# 初始化求最大且没有负值初始化为 0便于覆盖dp [0] * (bagWeight 1)dp[0] 0# 递推关系dp[j] max(dp[j], dp[j-weight[i]]value[i])# 01背包问题——先遍历物体再遍历背包容量for i in range(N): # 遍历物体for j in range(bagWeight,weights[i]-1,-1): # 倒序遍历背包容量for k in range(1,nums[i]1): # 遍历物体数量if j - k * weights[i] 0: # 乘以 k 是因为一维滚动数组的潜在含义依次遍历物体的种类dp[j] max(dp[j], dp[j- k * weights[i]] k * values[i]) else:breakreturn dp[bagWeight]if __name__ __main__:# 调用函数并获取输入的数字列表C, N, weights, values, nums read_input()print(maxValue(C,N,weights,values,nums))
三、刷题提示 3.1 递推关系种类 3.1.1 装满背包max dp[j] max(dp[j], dp[j - weight[i]] value[i]) 分割等和子集 最后一块石头的重量 一和零 3.1.2 装满背包的方法数 dp[j] min(dp[j - coins[i]] 1, dp[j]) 目标和 零钱兑换 II 组合总和 IV 爬楼梯的进阶版 3.1.3 装满背包的最小数量 dp[j] dp[j - nums[i] 零钱兑换 完全平方数 3.2 遍历背包的顺序 3.2.1 完全背包的组合问题 先遍历物体再遍历背包容量 零钱兑换 II 3.2.2 完全背包的排列问题 先遍历背包容量再遍历物体 组合总和 IV 爬楼梯的进阶版 3.3 求最小数 内外循环遍历顺序不影响最终结果 零钱兑换 完全平方数
