for c = 0..W:

dp[0][c] = 0

for i = 1..n:

for c = 0..W:

if w[i] > c:

dp[i][c] = dp[i-1][c]

else:

dp[i][c] = max(

dp[i-1][c],

dp[i-1][c - w[i]] + v[i]

)

return dp[n][W]

—

function KNAPSACK_0_1(n, W, weight[1..n], value[1..n])

// n : 物品数量

// W : 背包容量

// weight[1..n]: 每件物品的重量

// value[1..n] : 每件物品的价值

// dp[i][j] : 前 i 件物品，背包容量为 j 时的最大价值

// 1. 初始化第一行（0 件物品时，任意容量价值为 0）

for j = 0 to W

dp[0][j] = 0 // 没有物品可以放，价值自然为 0

// 2. 遍历每一件物品

for i = 1 to n

// 3. 遍历每种背包容量

for j = 0 to W

if j < weight[i] // 背包容量不足以放下第 i 件物品

dp[i][j] = dp[i-1][j] // 只能选择不放第 i 件物品

else // 背包容量足够

// max(不放第 i 件物品, 放第 i 件物品后的价值)

dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i])

// dp[i-1][j] : 不放第 i 件，价值等于上一个物品状态

// dp[i-1][j-weight[i]] + value[i] : 放第 i 件，价值 = 剩余容量最优 + 当前物品价值

// 4. 返回最终答案：前 n 件物品，背包容量为 W 时的最大价值

return dp[n][W]