设0/1背包问题实例(w1,w2,w3,w4)=(10,15,6,9), (p1,p2,p3,p4)=(2,5,8,1)，M=35，求函数阶跃点的序偶集合（0≤i≤4），并给出决策序列。

我们可以使用动态规划来解决这个问题。设f[i][j]表示前i个物品放入容量为j的背包中能够得到的最大价值，则状态转移方程为：

f[i][j] = max{f[i-1][j], f[i-1][j-w[i]] + p[i]}，其中w[i]表示第i个物品的重量，p[i]表示第i个物品的价值。

根据状态转移方程，我们可以逐步计算f[i][j]的值。具体地，我们可以先计算出f[0][0...M]的值，然后依次计算f[1][0...M]、f[2][0...M]、f[3][0...M]、f[4][0...M]的值。

计算过程如下表所示：

| i\j | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | 0 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 |
| 2 | 0 | 0 | 0 | 0 | 0 | 2 | 2 | 2 | 2 | 2 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 |
| 3 | 0 | 0 | 0 | 0 | 0 | 2 | 2 | 2 | 2 | 8 | 8 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 |
| 4 | 0 | 0 | 0 | 0 | 1 | 2 | 2 | 2 | 2 | 8 | 8 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 11 | 11 | 11 | 11 | 11 | 11 | 11 | 11 | 11 | 11 | 11 | 11 | 11 | 11 | 11 | 11 |

我们可以看到，当j=2时，f[1][2]发生了变化，因此(1,2)是函数阶跃点之一；当j=5时，f[2][5]发生了变化，因此(2,5)是函数阶跃点之一；当j=10时，f[3][10]发生了变化，因此(3,10)是函数阶跃点之一；当j=11时，f[4][11]发生了变化，因此(4,11)是函数阶跃点之一。

决策序列为：(4,11)→(3,10)→(2,5)→(1,2)→(0,0)。