# 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])