"""
背包问题按照可选样本的数量有无限制，可分为0-1背包问题和完全背包问题。但是，不管0-1背包问题，还是完全背包问题他们的状态
都是dp[i][j]表示前i个选择中，背包容量j的情况，
选择：都是是否选择加入该i
"""

"""
0-1背包问题：
给你⼀个可装载重量为 W 的背包和 N 个物品，每个物品有重量和价值两个属性。其中第 i 个物品的重量为 wt[i] ，价值为 val[i] ，
现在让你⽤这个背包装物品，最多能装的价值是多少
例如：
N = 3, W = 4
wt = [2, 1, 3]
val = [4, 2, 3]
output=6

解题思路：
dp[i][w] 表示前i个物品且背包容量为w时，最多能够装的价值
状态转移矩阵：
dp[i][w] = max(dp[i-1][w]) , dp[i-1][w-wt[i-1]] + val_list[i-1])表示背包不选择/选择加入当前产品的做大价值
base case: dp[0][...]=0, 没有可选的产品，最大价值为0
dp[...][0]=0，背包没有容量，最大价值为0
"""
def packsack_problem_0_1(val_n, val_w, wt, val_list):
    dp = [[0 for _ in range(val_w+1)] for _ in range(val_n+1)] #定义dp数组，覆盖了base case, 故不用重新声明base case
    for i in range(1, val_n + 1):
        for w in range(1, val_w + 1):
            if w < wt[i-1]: #当前背包的容量小于该产品的容量，只能不选择该产品
                dp[i][w] = dp[i-1][w]
            else: #比较选择和不选择价值最大
                dp[i][w] = max(dp[i-1][w], dp[i-1][w-wt[i-1]] + val_list[i-1])
    return dp[val_n][val_w]

"""
根据0-1问题，可以解决子集分割问题
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
注意：
1.每个数组中的元素不会超过100
2.数组的大小不会超过200
示例：
输入：[1,5,11,5]
输出：true

解题思路：
这道题可以转化为：背包大小为sum(input)/2的0-1背包问题
状态转移矩阵定义：bp[i][w] 表示前i索引值的和是否等于w
base case:
dp[...][0]=True 表示前i索引都不进行选择，w=0可以实现
dp[0][...]=False 表示前0个索引无论如何都不可能等于w
选择：
if j >= list_nums[i-1]:
    dp[i][j] = dp[i-1][j] | dp[i-1][j-list_nums[i-1]] #状态转移矩阵
else:
    dp[i][j] = dp[i - 1][j]
"""
def split_subset(list_nums):
    sums = sum(list_nums)
    if sums % 2 != 0:
        return False
    target = int(sums / 2) #相当于背包的容量
    dp = [[False for i in range(target + 1)] for j in range(len(list_nums) + 1)]
    for i in range(len(dp)):
        dp[i][0] = True
    #base case
    for i in range(1, len(list_nums) + 1):
        for j in range(1, target+1):
            if j >= list_nums[i-1]:
                dp[i][j] = dp[i-1][j] | dp[i-1][j-list_nums[i-1]] #状态转移矩阵
            else:
                dp[i][j] = dp[i - 1][j]
    return dp[len(list_nums)][target]


#完全背包问题（凑零钱问题），样本的数量没有限制

"""
案例：
给定不同面额的硬币和一个总金额，写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个
输入：amount=5, coins=[1,2,5]
输出：4
"""
def make_the_change(coins, amount):
    dp = [[0 for i in range(amount + 1)] for j in range(len(coins) + 1)] #定义状态转移矩阵， 前i个零钱凑出总数为j的组合数
    for i in range(len(dp)):
        dp[i][0] = 1 #base case
    for i in range(1, len(coins) + 1):
        for j in range(1, amount + 1):
            if j >= coins[i - 1]:
                dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i - 1]] #状态转移
            else:
                dp[i][j] = dp[i - 1][j]

    return dp[len(coins)][amount]

#凑零钱问题变种
"""
给你 k 种⾯值的硬币，⾯值分别为 c1, c2 ... ck ，每种硬币的数量⽆限，再给⼀个总⾦额 amount ，问你最少需要⼏枚硬币凑出这个
⾦额，如果不可能凑出，算法返回 -1 。
⽐如说 k = 3 ，⾯值分别为 1，2，5，总⾦额 amount = 11 。那么最少需要 3 枚硬币凑出，即 11 = 5 + 5 + 1。
"""
def coin_change(coins, amount):
    def dp(n):
        # base case
        if n == 0: return 0
        if n < 0: return -1
        # 求最⼩值，所以初始化为正⽆穷
        res = float('INF')
        for coin in coins:
            subproblem = dp(n - coin)
            # ⼦问题⽆解，跳过
            if subproblem == -1: continue
            res = min(res, 1 + subproblem)
        return res if res != float('INF') else -1
    return dp(amount)

def coin_change(coins, amount):
    dp = [amount + 1 for _ in range(amount+1)]
    dp[0] = 0
    for i in range(len(dp)):
        for coin in coins:
            if i - coin < 0:continue
            dp[i] = min(dp[i], 1 + dp[i-coin])
    return -1 if dp[amount] == amount + 1 else dp[amount]

if __name__ == "__main__":
    N = 3
    W = 4
    wt = [2, 1, 3]
    val = [4, 2, 3]
    res = packsack_problem_0_1(N, W, wt, val)
    print(res)