1、给你一个可装载重量为 W 的背包和 N 个物品，每个物品有重量和价值两个属性。其中第 i 个物品的重量为 wt[i]，价值为 val[i]，现在让你用这个背包装物品，最多能装的价值是多少？
思路：0-1背包问题，注意dp[ ]的定义，状态转移的公式，
# dp[N][W] 代表 对于前 i 个物品，当前背包的容量为 w，这种情况下可以装的最大价值是dp[i][w] def knapsack(W, N, wt, val): dp = [[0 for i in range(W+1)] for j in range(N+1)] for i in range(1, N+1): for w in range(1, W+1): if w - wt[i-1] < 0: # 如果重量超重，保留之前的价值 dp[i][w] = dp[i-1][w] else: # 如果重量没有超重，之前价值 和 当前的价值 取最大值 dp[i][w] = max(dp[i-1][w-wt[i-1]] + val[i-1], dp[i-1][w]) print(dp) return dp[N][W]
2、完全背包问题，即必须刚好填满背包，而01背包是可以少于背包空间
思路：定义dp[ ]，定义转移方程，初始化
def change(self, amount: int, coins: List[int]) -> int: # 问题可以转化为背包问题 # 定义dp[i][j]， 表示为前i个硬币中，凑够j金额，的方法 # 定状态转移公式： 不装进背包，保留前一个 -- dp[i][j] = dp[i-1][j] # 装进背包，当前的数目 + 前一个方法数 -- dp[i][j] = dp[i-1][j-coins[i-1]] + dp[i-1][j] n = len(coins) dp = [[0 for i in range(amount+1)] for j 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: # 超过金额数目,则令前i-1个物体的方法数 等于 当前方法数 dp[i][j] = dp[i-1][j] else: dp[i][j] = dp[i][j-coins[i-1]] + dp[i-1][j] # 综合两种方法，即放进包和不放进包 return dp[n][amount]