算法可视化
入门执行逻辑
0/1 背包:动态规划填表
每个物品只能拿或不拿,求容量限制下的最大价值。dp[i][c] 表示前 i 个物品、容量 c 的最大价值,逐个填表。
main.cpp第 3 行
1// 0/1 背包: 4 个物品, 容量 5
2// 物品: (w,v) = (2,3)(3,4)(4,5)(5,6)
3for (int i = 1; i <= n; i++)
4 for (int c = 0; c <= W; c++)
5 if (w[i] <= c)
6 dp[i][c] = max(dp[i-1][c], dp[i-1][c-w[i]] + v[i]);
7 else
8 dp[i][c] = dp[i-1][c];
变量表0 个变量
还没有变量,执行到声明语句后出现
DP 表格(行=前 i 个物品, 列=容量)
| 物品 | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 1(w2,v3) | 0 | 0 | 0 | 0 | 0 | 0 |
| 2(w3,v4) | ||||||
| 3(w4,v5) | ||||||
| 4(w5,v6) | ||||||
| 4 |
本格取物品本格不取最优路径
1/40
dp 表格初始化:第 0 行全为 0(没有物品,价值都是 0)
1 / 40