算法打卡day38
今日任务：
1）完全背包理论基础(卡码网52. 携带研究材料)
2）518.零钱兑换II
3）377. 组合总和 Ⅳ
4）复习day13
完全背包理论基础(卡码网52. 携带研究材料)
题目链接：52. 携带研究材料（第七期模拟笔试） (kamacoder.com)
题目描述 小明是一位科学家，他需要参加一场重要的国际科学大会，以展示自己的最新研究成果。他需要带一些研究材料，但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等，它们各自占据不同的重量，并且具有不同的价值。 小明的行李箱所能承担的总重量为 N，问小明应该如何抉择，才能携带最大价值的研究材料，每种研究材料可以选择无数次，并且可以重复选择。 输入描述 第一行包含两个整数，N，V，分别表示研究材料的种类和行李空间 接下来包含 N 行，每行两个整数 wi 和 vi，代表第 i 种研究材料的重量和价值 输出描述 输出一个整数，表示最大价值。 输入示例 4 5 1 2 2 4 3 4 4 5 输出示例 10 提示信息 第一种材料选择五次，可以达到最大值。 数据范围： 1 <= N <= 10000; 1 <= V <= 10000; 1 <= wi, vi <= 10^9.
文章讲解：代码随想录 (programmercarl.com)
视频讲解：带你学透完全背包问题！ 和 01背包有什么差别？遍历顺序上有什么讲究？哔哩哔哩bilibili
思路：
这是一个典型的完全背包问题，与传统的0-1背包问题略有不同，因为每种研究材料可以选择无数次，并且可以重复选择。这种情况下，我们可以采用动态规划来解决。
01背包问题不能重复，所以我们用一维滚动数组时都是采用从后往前遍历，为了避免重复
而现在我们完全背包问题可以重复，所以我们在遍历物品时从前往后面遍历
初始化动态规划数组： 创建一个一维动态规划数组
dp，其长度为V+1，并将所有元素初始化为0。这里dp[i]表示在背包容量为i时能够获得的最大价值。遍历研究材料： 对于每一种研究材料，我们可以选择将其放入背包中，也可以选择不放入。
动态规划更新： 遍历研究材料时，对于每一种材料，我们需要更新动态规划数组。具体地，我们从容量为
wi的背包开始遍历，逐步向上更新动态规划数组中的值。状态转移方程为：dp[i] = max(dp[i], dp[i - wi] + vi)，表示在容量为i的背包中，我们可以选择不放入当前材料，也可以选择放入当前材料，取两者中的最大值。返回结果： 最后返回动态规划数组中的最大值，即为可以获得的最大价值。
输入示例
3 4
1 15
3 20
4 30
输出示例 60
def test_CompletePack(weight, value, bagweight):
# 创建一维数组用于存储当前背包容量下的最大价值
dp = [0] * (bagweight + 1)
# 遍历每种研究材料
for i in range(len(weight)):
# 遍历背包容量
for j in range(weight[i], bagweight + 1):
# 如果当前背包容量 j 大于等于当前物品的重量 weight[i]，
# 则可以选择放入当前物品，比较放入当前物品与不放入当前物品的价值大小，取较大者更新 dp[j]
dp[j] = max(dp[j], value[i] + dp[j - weight[i]])
# 返回能够携带的研究材料的最大价值
return dp[-1]
if __name__ == "__main__":
# 获取研究材料的种类 N 和小明的行李空间 N
N, bagweight = map(int, input().split())
weight = []
value = []
# 获取每种研究材料的空间和价值
for _ in range(N):
# 采集每种研究材料的重量和价值
wi, vi = map(int, input().split())
# 将重量和价值组成的列表添加到材料列表中
weight.append(wi)
value.append(vi)
# 调用函数计算最大价值并输出结果
result = test_CompletePack(weight, value, bagweight)
print(result)518.零钱兑换II
题目链接：518. 零钱兑换 II - 力扣（LeetCode）
给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。 示例 1: 输入: amount = 5, coins = [1, 2, 5] 输出: 4 解释: 有四种方式可以凑成总金额: 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1 示例 2: 输入: amount = 3, coins = [2] 输出: 0 解释: 只用面额2的硬币不能凑成总金额3。 示例 3: 输入: amount = 10, coins = [10] 输出: 1 注意，你可以假设： 0 <= amount (总金额) <= 5000 1 <= coin (硬币面额) <= 5000 硬币种类不超过 500 种 结果符合 32 位符号整数
文章讲解：代码随想录 (programmercarl.com)
视频讲解：动态规划之完全背包，装满背包有多少种方法？组合与排列有讲究！| LeetCode：518.零钱兑换II哔哩哔哩bilibili
思路：
- 使用动态规划来解决问题，其中 dp[i] 表示凑成总金额 i 的硬币组合数。
- 初始化 dp 列表，将 dp[0] 置为 1，表示凑成金额为 0 的组合只有一种，即什么也不选。
- 遍历硬币列表 coins，对于每个硬币面额 coin，从 coin 到 amount 进行遍历，更新 dp[j]。
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
dp = [0]*(amount+1)
dp[0] = 1
# 遍历物品
# print(dp)
for coin in coins:
# 遍历背包
for j in range(coin, amount+1):
dp[j] = dp[j] + dp[j-coin]
# print(dp)
return dp[-1]377. 组合总和 Ⅳ
题目链接：377. 组合总和 Ⅳ - 力扣（LeetCode）
难度：中等 给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。 示例: nums = [1, 2, 3] target = 4 所有可能的组合为： (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1) 请注意，顺序不同的序列被视作不同的组合。 因此输出为 7。
文章讲解：代码随想录 (programmercarl.com)
视频讲解：动态规划之完全背包，装满背包有几种方法？求排列数？| LeetCode：377.组合总和IV哔哩哔哩bilibili
思路：
本题题目描述说是求组合，但又说是可以元素相同顺序不同的组合算两个组合，其实就是求排列！
弄清什么是组合，什么是排列很重要。
组合不强调顺序，(1,5)和(5,1)是同一个组合。
排列强调顺序，(1,5)和(5,1)是两个不同的排列。
上一题518. 零钱兑换 II - 力扣（LeetCode）就是求组合
而本题是求排列
如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。
- 使用动态规划来解决问题，其中 dp[i] 表示和为 i 的组合个数。
- 初始化 dp 列表，将 dp[0] 置为 1，表示和为 0 的组合只有一种，即什么也不选。
- 遍历目标值 j 从 1 到 target，对于每个目标值 j，遍历数组 nums 中的每个数 num，更新 dp[j]
先更新第0列
更新第1列
更新第2列
更新第3列
更新第4列
最终状态
class Solution:
def combinationSum4(self, nums: List[int], target: int) -> int:
dp = [0]*(target+1)
dp[0] = 1
# 遍历背包
print(dp)
for j in range(1, target + 1):
# 遍历物品
for num in nums:
# 当背包容量大于等于当前物品重量时,更新组合总数
if j>=num:
dp[j] = dp[j] + dp[j-num]
print(dp)
# 返回背包容量为target时的组合总数
return dp[-1]原文地址：https://blog.csdn.net/wenxiaohai123/article/details/136547486
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！