【算法-面试】动态规划专题之背包问题
2022/1/30 17:04:42
本文主要是介绍【算法-面试】动态规划专题之背包问题,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
# coding = "utf-8" ''' 0-1背包:https://mp.weixin.qq.com/s?__biz=MzAxODQxMDM0Mw==&mid=2247485064&idx=1&sn=550705eb67f5e71487c8b218382919d6&chksm=9bd7f880aca071962a5a17d0f85d979d6f0c5a5ce32c84b8fee88e36d451f9ccb3bb47b88f78&scene=21#wechat_redirect dp[i][j]:前i个物品,背包容量为j,此时的最大价值 状态: 1. 装进背包(放得下) 2. 不装进背包(放不下) 子集背包: 完全背包:物品数量是无上限的 ''' def canPartition(nums): ''' 给你⼀个只包含正整数的⾮空数组 nums。请你判断是否可以将这个数组分割成两个⼦集,使得两个⼦集的元素和相等。 leetcode:416. 分割等和⼦集 input:nums = [1,5,11,5] output:true 思路: 1. 转换问题:给一个可装载重量为sum/2的背包和N个物品,每个物品的重量为nums[i]。现在让你装物品,是否存在一种装法,能够恰好将背包装满 2. dp[i][j] = x表示,对于前i个物品,当前背包的容量为j时,若x为true,则说明可以恰好将背包装满,若x为false,则说明不能恰好将背包装满 3. ''' n, s = len(nums), sum(nums) if s % 2 != 0: return False s = int(s / 2) dp = [[False for _ in range(s + 1)] for _ in range(n + 1)] for i in range(n + 1): # base case # 因为背包没有空间的时候,就相当于装满了;而当没有物品可选择的时候,肯定没办法装满背包 dp[i][0] = True for i in range(1, n + 1): for j in range(1, s + 1): print(nums[i - 1], j - nums[i - 1]) if j - nums[i - 1] < 0: # 装不下 dp[i][j] = dp[i - 1][j] else: # 装得下 如果不装,则取决于上一个状态;如果装,则取决于背包剩余容量的状态 dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i - 1]] print(dp[n][s]) return dp[n][s] def findTargetSumWays(nums, target): ''' 给你⼀个整数数组 nums 和⼀个整数 target,向数组中的每个整数前添加 '+' 或 '-',然后串联起所有整数,可以构造⼀个表达式。 例如,nums = [2, 1],可以在 2 之前添加 '+',在 1 之前添加 '-',然后串联起来得到表达式 "+2-1"。 返回可以通过上述⽅法构造的、运算结果等于 target 的不同表达式的数⽬。 leetcode:494. ⽬标和 input:nums = [1,1,1,1,1], target = 3 output:5 思路: 1. 此题可以使用回溯法做 2. 动态规划做法是转化问题,sum(A) = (target + sum(nums)) / 2 nums 中存在几个子集 A,使得 A 中元素的和为 (target + sum(nums)) / 2? 3. ''' n, s = len(nums), sum(nums) if s < target or (s + target) % 2 == 1: return 0 s = int((s + target) / 2) dp = [[0 for _ in range(s + 1)] for _ in range(n + 1)] for i in range(n + 1): # base case 背包为0的时候,不放入也是一种选择 dp[i][0] = 1 for i in range(1, n + 1): for j in range(1, s + 1): if j - nums[i - 1] < 0: dp[i][j] = dp[i - 1][j] else: dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i - 1]] print(dp[n][s]) return dp[n][s] def change(amount, coins): ''' 给你⼀个整数数组 coins 表示不同⾯额的硬币(硬币个数⽆限),另给⼀个整数 amount 表示总⾦额。 请你计算并返回可以凑成总⾦额的硬币组合数,如果任何硬币组合都⽆法凑出总⾦额,返回 0。 leetcode: 518. 零钱兑换 II input: amount = 5, coins = [1, 2, 5] output: 4 思路: 1. 2. 3. ''' n = len(coins) dp = [[0 for _ in range(amount + 1)] for _ in range(n + 1)] for i in range(n + 1): dp[i][0] = 1 for i in range(1, n + 1): for j in range(1, amount + 1): if j - coins[i - 1] < 0: dp[i][j] = dp[i - 1][j] else: # 由于硬币是无限的,所以不选择该硬币时,dp[i][j - coins[i - 1]] dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i - 1]] print(dp[n][amount]) return dp[n][amount] if __name__ == "__main__": # canPartition([1, 5, 11, 5]) # findTargetSumWays([1, 1, 1, 1, 1], 3) change(5, [1, 2, 5])
这篇关于【算法-面试】动态规划专题之背包问题的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现
- 2024-05-30我们小公司,哪像华为一样,用得上IPD(集成产品开发)?
- 2024-05-30java excel上传--poi
- 2024-05-30安装笔记本应用商店的pycharm,再安排pandas等模块,说是没有打包工具?
- 2024-05-29java11新特性