01背包-动态规划 f[j]=max(f[j], f[j-w[i]] +c[i])

**01 背包 - 动态规划**

**概述**

01 背包问题是一种经典的动态规划问题。背包问题描述的是：有一袋子装有不同重量和价值的物品，我们需要在不超过总重量限制的情况下，选择哪些物品放入背包，以使得背包中的物品总价值最大。

**动态规划**

动态规划是一种解决复杂问题的方法，它通过分解问题、建立状态转移方程和计算最优解来实现。01 背包问题可以使用动态规划来求解。

**状态定义**

在01 背包问题中，我们需要定义一个状态变量 `f[j]`，表示背包容量为 `j` 时的最大价值。

**状态转移方程**

状态转移方程是01 背包问题中的关键。它描述的是：当我们选择放入背包的物品时，背包的容量会减少 `w[i]`，而价值会增加 `c[i]`。因此，我们可以写出以下状态转移方程：

f[j] = max(f[j], f[j-w[i]] + c[i])

def knapsack(W, Wt, c, n):
 # 初始化状态变量 dp = [0 for _ in range(len(W) +1)]

 # 遍历物品 for i in range(1, n +1):
 # 遍历背包容量 for j in range(len(W), -1, -1):
 # 如果当前物品的重量超过背包容量，则跳过 if Wt[i-1] > j:
 dp[j] = dp[j]
 else:
 # 计算状态转移方程 dp[j] = max(dp[j], dp[j-Wt[i-1]] + c[i-1])

 return dp[-1]

# 测试数据W = [2,3,4,5]
Wt = [3,4,5,6]
c = [10,20,30,40]
n = len(W)

print(knapsack(W, Wt, c, n)) # 输出：90