1.(5分)在一般背包问题中，有载重为15的背包，4件物品的重量分别为: (wO,w1,w2,w3)=(4,5,3,6)，物品装入背包的收益为:(p0.p1,p2,p3)=(20,18,15,22)，设问题的解为(x0,x1,x2,x3)，当解为（）时，物品装入背包可获得最大收益。

解题思路：

使用动态规划的思想，设f[i][j]为前i个物品放入载重为j的背包中所能获得的最大收益。则对于第i个物品，可以选择放入或不放入背包中，因此可以得到状态转移方程：

f[i][j] = max(f[i-1][j], f[i-1][j-w[i]]+p[i])

其中，w[i]为第i个物品的重量，p[i]为第i个物品的收益。边界条件为f[0][j]=0（前0个物品放入任意载重的背包中的最大收益为0），f[i][0]=0（任意物品放入载重为0的背包中的最大收益为0）。

根据状态转移方程，可以得到如下的动态规划表格：

| 物品 \ 载重 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
|:-----------:|---|---|---|---|---|---|---|---|---|---|----|----|----|----|----|----|
| 0 | 0 | 0 | 0 | 0 | 20| 20| 20| 20| 20| 20| 20 | 20 | 20 | 20 | 20 | 20 |
| 1 | 0 | 0 | 0 | 0 | 20| 18| 18| 18| 18| 18| 38 | 38 | 38 | 38 | 38 | 38 |
| 2 | 0 | 0 | 0 | 15| 20| 20| 18| 33| 33| 33| 38 | 38 | 38 | 53 | 53 | 53 |
| 3 | 0 | 0 | 0 | 15| 20| 20| 22| 37| 35| 35| 40 | 60 | 60 | 60 | 60 | 60 |
| 4 | 0 | 0 | 0 | 15| 20| 20| 22| 37| 35| 35| 40 | 60 | 60 | 62 | 77 | 75 |

因此，当解为(x0,x1,x2,x3)=(0,1,1,1)时，物品装入背包可获得最大收益为75。

代码实现：

w = [0, 4, 5, 3, 6]
p = [0, 20, 18, 15, 22]
n = len(w) - 1
m = 15
f = [[0] * (m + 1) for i in range(n + 1)]
for i in range(1, n + 1):
    for j in range(1, m + 1):
        if j >= w[i]:
            f[i][j] = max(f[i-1][j], f[i-1][j-w[i]] + p[i])
        else:
            f[i][j] = f[i-1][j]
print(f[n][m])