背包问题 - 动态规划算法讲解

0/1 Knapsack Problem - 理解动态规划的核心思想

物品列表

背包容量: 10

A

物品A

2 6

B

物品B

2 3

C

物品C

6 5

D

物品D

5 4

E

物品E

4 6

状态转移方程

dp[i][w] = 前 i 个物品，容量 w 的最大价值

if w < weight[i]:

dp[i][w] = dp[i-1][w]

else:

dp[i][w] = max(

dp[i-1][w], // 不选

dp[i-1][w-weight[i]] + value[i] // 选择

)

DP Table 动态规划表格步骤: 0 / 67

i \ w

0

1

2

3

4

5

6

7

8

9

10

空

-

-

-

-

-

-

-

-

-

-

-

+A

-

-

-

-

-

-

-

-

-

-

-

+B

-

-

-

-

-

-

-

-

-

-

-

+C

-

-

-

-

-

-

-

-

-

-

-

+D

-

-

-

-

-

-

-

-

-

-

-

+E

-

-

-

-

-

-

-

-

-

-

-

当前计算

比较位置

已计算

未计算

步骤讲解

开始填充DP表格。dp[i][w]表示前i个物品在容量w下的最大价值。

播放速度:中