设有0/1背包实例(w0, w1, w2 w3)=(10, 15, 6, 9), (P0,P1,P2,P3)=(2,5,8, 1)和M=32。试计算s',0≤i≤4。另使用启发式方法再计算一次。

根据0/1背包的动态规划算法，可以得到以下状态转移方程：
s[i][j] = max{s[i-1][j], s[i-1][j-w[i]] + p[i]} (j>=w[i])
其中，s[i][j]表示前i个物品放入容量为j的背包中所能获得的最大价值，w[i]表示第i个物品的重量，p[i]表示第i个物品的价值。

根据这个方程，可以得到以下表格：

| i | j | s[i][j] |
| --- | --- | --------- |
| 0 | 0 | 0 |
| 1 | 0 | 0 |
| 1 | 10 | 2 |
| 1 | 15 | 5 |
| 2 | 0 | 0 |
| 2 | 10 | 2 |
| 2 | 15 | 5 |
| 2 | 16 | 8 |
| 2 | 25 | 10 |
| 2 | 30 | 13 |
| 3 | 0 | 0 |
| 3 | 6 | 2 |
| 3 | 9 | 3 |
| 3 | 10 | 2 |
| 3 | 15 | 5 |
| 3 | 16 | 8 |
| 3 | 21 | 7 |
| 3 | 24 | 10 |
| 3 | 25 | 13 |
| 3 | 30 | 15 |
| 4 | 0 | 0 |
| 4 | 1 | 2 |
| 4 | 6 | 5 |
| 4 | 9 | 6 |
| 4 | 10 | 7 |
| 4 | 15 | 10 |
| 4 | 16 | 13 |
| 4 | 21 | 12 |
| 4 | 24 | 15 |
| 4 | 25 | 18 |
| 4 | 30 | 20 |

其中，s'[i]表示前i个物品放入容量为M的背包中所能获得的最大价值，因此s'[4]即为最终答案，为20。

对于启发式方法，可以将物品按单位重量的价值从大到小排序，然后依次放入背包中。具体步骤如下：

1. 计算每个物品的单位重量价值：v[i] = p[i]/w[i]
2. 按照单位重量价值从大到小的顺序将物品排序
3. 依次将物品放入背包中，直到背包无法再放下物品为止

按照这个方法，可以得到以下过程：

| 物品 | 重量 | 价值 | 单位重量价值 | 背包剩余容量 | 背包价值 |
| ------ | ------ | ------ | -------------- | ------------- | ---------- |
| P2 | 6 | 8 | 1.33 | 26 | 8 |
| P1 | 15 | 5 | 0.33 | 11 | 13 |
| P0 | 10 | 2 | 0.20 | 1 | 15 |
| P3 | 9 | 1 | 0.11 | 0 | 16 |

因此，启发式方法得到的最大价值为16，与动态规划方法得到的结果不同。