算法打卡day40

今日任务：

1）139.单词拆分

2）多重背包理论基础（卡码网56携带矿石资源）

3）背包问题总结

4）复习day15

139单词拆分

题目链接：139. 单词拆分 - 力扣（LeetCode）

给定一个非空字符串 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

文章讲解：代码随想录 (programmercarl.com)

视频讲解：动态规划之完全背包，你的背包如何装满？| LeetCode：139.单词拆分哔哩哔哩bilibili

思路：

字典里的单词是可以被重复的，这是一个完全背包问题。字符串中的单词是有序的，所以相当于是做排列问题，应该先遍历背包，再遍历物品

这里的s字符串就是背包：创建数组dp[j]，不断更新dp[j]的值为True或False。也就是如果s[:j]能拆分，则dp[j] 为True

这里的单词就是物品：我们的目标是检查是否可以将字符串拆分为字典中的单词，这里有两种处理方法，一种是遍历字典中的单词，判断其在背包中能否拆分出来，有一个单词能被拆分都行；另一种是在s[:j]的每一个位置切分，判断s[i:j]是否存在字典中

class Solution:def wordBreak(self, s: str, wordDict: List[str]) -> bool:dp = [False] * len(s)dp.insert(0, True)# print(dp)for j in range(1, len(s) + 1):for word in wordDict:lenth = len(word)if j >= lenth:dp[j] = dp[j] or (dp[j-lenth] and word == s[j-lenth : j])# print(f'当物品为{word}时，dp[{j}]={dp[j]}')# print(f'此时j={j},dp={dp}')return dp[-1]def wordBreak2(self, s: str, wordDict: List[str]) -> bool:# 初始化动态规划数组，dp[j]表示s的前j个字符是否可以被拆分成字典中的单词dp = [False] * (len(s)+1)dp[0] = True# 将字典中的单词转换为集合，便于快速判断单词是否在字典中word_set = set(wordDict)# 遍历背包for j in range(1,len(s)+1):# print(f'j={j}')# 在背包大小的字符串s[:j]中寻找分割点(s[left:right]左闭右开)，看是否存在以s[j]结尾的单词for i in range(j+1):# print(s[i:j])# 如果前i个字符可以被拆分且s[i:j]在字典中，则将dp[j]设置为Trueif s[i:j] in word_set and dp[i]:dp[j] = Truebreak# 返回整个字符串s是否可以被拆分return dp[-1]

感想：

这题要注意i，j分别在dp和s中表示什么。很容易弄错，自己画图比较清晰
这里有一个优化，我们将字典中的单词转换为集合，便于快速判断单词是否在字典中

假设我们有一个单词列表 wordDict，其中包含了若干个单词。如果我们将这个列表转换为集合 wordSet，则每个单词就会成为 wordSet 中的一个元素。这样，当我们需要判断某个单词是否在字典中时，只需要使用集合的 in 操作符即可。这个操作会以常量时间（O(1)）内完成，因为集合底层使用哈希表实现，可以快速地定位元素。

相比之下，如果我们使用列表来表示字典，那么在判断单词是否在字典中时，需要遍历整个列表，时间复杂度会是 O(n)，其中 n 是字典中单词的数量。这样的时间复杂度在实际应用中可能会较高，尤其是当字典中包含大量单词时。

因此，将字典中的单词转换为集合后，能够以更高效的方式进行单词的查找，从而加快了判断字符串是否可以被拆分的速度。

多重背包理论基础（卡码网56携带矿石资源）

题目链接：56. 携带矿石资源（第八期模拟笔试） (kamacoder.com)

题目描述
你是一名宇航员，即将前往一个遥远的行星。在这个行星上，有许多不同类型的矿石资源，每种矿石都有不同的重要性和价值。你需要选择哪些矿石带回地球，但你的宇航舱有一定的容量限制。
给定一个宇航舱，最大容量为 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;

文章讲解：代码随想录 (programmercarl.com)

思路：

这个问题可以使用动态规划来解决。我们可以定义一个二维数组 dp[i][j]，其中 dp[i][j] 表示前 i 种矿石，容量为 j 的情况下所能获取的最大价值。

具体的动态规划转移方程为：

$dp[i][j] = \max(dp[i-1][j], dp[i-1][j - w[i]] + v[i],dp[i-1][j-2*w[i]]+2*v[i],...,dp[i-1][j-k[i]*w[i]]+k[i]*v[i])$

其中，dp[i−1][j−w[i]]+v[i] 表示选择了第 i 种矿石，并且当前容量为 j，剩余容量为 j-w[i] 时的最大价值，加上选取当前矿石所获得的价值 v[i]。

根据这个方程，我们可以进行动态规划计算，最终得到dp[N][C]，即前 N 种矿石，容量为 C 时所能获取的最大价值。

def max_value():# 从键盘上采集输入数据C, N = map(int, input().split())  # 宇航舱的容量和矿石的种类数量weights = list(map(int, input().split()))  # 矿石的重量values = list(map(int, input().split()))  # 矿石的价格limits = list(map(int, input().split()))  # 矿石的可用数量上限# 创建二维动态规划数组，初始化为0dp = [[0] * (C + 1) for _ in range(N + 1)]# 遍历每种矿石for i in range(1, N + 1):# 遍历容量for j in range(1, C + 1):# 当前容量 j 不足以装下当前矿石 i 时，不选择该矿石dp[i][j] = dp[i - 1][j]# 遍历当前矿石可用数量上限for k in range(1, min(j // weights[i - 1], limits[i - 1]) + 1):# 计算选择 k 个当前矿石 i 后的总价值dp[i][j] = max(dp[i][j], dp[i - 1][j - k * weights[i - 1]] + k * values[i - 1])# 返回前 N 种矿石，容量为 C 时的最大价值return dp[N][C]# 调用函数并输出结果
print(max_value())

这个函数的时间复杂度为 O(N * C * k_max)，其中 N 是矿石种类数量，C 是宇航舱的容量，k_max 是矿石的可用数量上限中的最大值。

采用一维dp数组解决，代码如下：

动态转移方程： $dp[j] = \max(dp[j], dp[j - k \times weights[i - 1]] + k \times values[i - 1])$

其中：

dp[j] 表示容量为 j 时的最大价值；
weights[i−1] 表示第 i 种矿石的重量；
values[i−1] 表示第 i 种矿石的价格；
k 表示选择的第 i 种矿石的数量， $1\leq k\leq min(\frac{j}{weight[i-1]},limit[i-1])$

def max_value2():# 从键盘上采集输入数据C, N = map(int, input().split())  # 宇航舱的容量和矿石的种类数量weights = list(map(int, input().split()))  # 矿石的重量values = list(map(int, input().split()))  # 矿石的价格limits = list(map(int, input().split()))  # 矿石的可用数量上限# 创建一维动态规划数组，初始化为0dp = [0] * (C + 1)# 遍历每种矿石for i in range(1, N + 1):# 逆序遍历容量，确保每个矿石只使用一次for j in range(C, 0, -1):# 遍历当前矿石可用数量上限for k in range(1, min(j // weights[i - 1], limits[i - 1]) + 1):# 计算选择 k 个当前矿石 i 后的总价值dp[j] = max(dp[j], dp[j - k * weights[i - 1]] + k * values[i - 1])# 返回容量为 C 时的最大价值return dp[C]# 调用函数并输出结果
print(max_value2())