背问问题

01背包

有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
使用动态规划5步曲处理。

01背包二维数组解法

1.确定dp数组以及下标的含义
对于背包问题，有一种写法， 是使用二维数组，即dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。

2.确定递推公式
由以下两个方向推出来dp[i][j]：

• 不放物品i：由dp[i - 1][j]推出，即背包容量为j，里面不放物品i的最大价值，此时dp[i][j]就是dp[i - 1][j]。(其实就是当物品i的重量大于背包j的重量时，物品i无法放进背包中，所以背包内的价值依然和前面相同。)
• 放物品i：由dp[i - 1][j - weight[i]]推出，dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最大价值，那么dp[i - 1][j - weight[i]] + value[i] （物品i的价值），就是背包放物品i得到的最大价值
• 递归公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

3.dp数组初始化

 # 二维数组
    dp = [[0] * (bagweight + 1) for _ in range(len(weight))]

    # 初始化
    for j in range(weight[0], bagweight + 1):
        dp[0][j] = value[0]

4.遍历顺序

 # weight数组的大小就是物品个数
 # 先遍历背包容量，再遍历物品也行
    for i in range(1, len(weight)):  # 遍历物品
        for j in range(bagweight + 1):  # 遍历背包容量
            if j < weight[i]:
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])

5.打印dp数组

print(dp[len(weight) - 1][bagweight])

01背包一维数组解法(滚动数组)

# 只能先遍历物品再遍历背包容量
# 遍历背包容量时只能倒序，确保每个物品只放一次
def test_1_wei_bag_problem():
    weight = [1, 3, 4]
    value = [15, 20, 30]
    bagWeight = 4

    # 初始化
    dp = [0] * (bagWeight + 1)
    for i in range(len(weight)):  # 遍历物品
        for j in range(bagWeight, weight[i] - 1, -1):  # 遍历背包容量
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i])

    print(dp[bagWeight])

完全背包

有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用无数次，求解将哪些物品装入背包里物品价值总和最大。

# 主要根据01背包一维数组解法修改，把遍历背包容量时的倒序改为正序。
# 此时for循环可颠倒顺序，先背包容量后物品
def test_CompletePack():
    weight = [1, 3, 4]
    value = [15, 20, 30]
    bagWeight = 4
    dp = [0] * (bagWeight + 1)
    for i in range(len(weight)):  # 遍历物品
        for j in range(weight[i], bagWeight + 1):  # 遍历背包容量
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
    print(dp[bagWeight])

凑东西有多少种方法(衍生)

记住递推公式：dp[j]+=dp[j-nums[i]]
例题：
给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
假设每一种面额的硬币有无限个。

# 此类问题为完全背包问题，就是从一个数组中凑一个数问有多少种方法
# 此题强调组合数，不考虑选出元素的排列顺序，所以先遍历物品后遍历背包容量
# 若强调有顺序的排列，则先遍历背包容量后遍历物品(结论)
# 此外，初始化dp[0]也需注意，一般为1
class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        dp=[0]*(amount+1)
        dp[0]=1
        ans=0
        for i in range(len(coins)):
            for a in range(coins[i],amount+1):
                dp[a]+=dp[a-coins[i]] 
        return dp[amount]