来源： https://www.acwing.com/problem/content/2/
推荐视频讲解： https://www.acwing.com/video/322/
题目描述：
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
根据闫氏DP法：
状态计算就是状态方程，所以： $ f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i])$ 这里$j - v[i] >= 0 $
所以伪代码如下：
1
2
3
4
5
6
7
| for i <- 0 to n:
for j <- 0 to m:
f[i][j] = f[i - 1][j]
if v[i] <= j:
f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i])
|
具体Python代码实现如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| N = 1010
dp = [[0]*N for _ in range(N)]
v = [0]*N
w = [0]*N
def main():
n, m = map(int, input().split())
for i in range(1, n + 1):
v[i], w[i] = map(int, input().split())
for i in range(1, n + 1):
for j in range(1, m + 1):
dp[i][j] = dp[i - 1][j]
if j >= v[i]:
dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i])
print(dp[n][m])
main()
|
根据dp表格所推出来的数据如下， 行表示物品i， 列表示背包容量v
| 0 |
1 |
2 |
3 |
4 |
5 |
| 0 |
0 |
0 |
0 |
0 |
0 |
| 0 |
2 |
2 |
2 |
2 |
2 |
| 0 |
2 |
4 |
6 |
6 |
6 |
| 0 |
2 |
4 |
6 |
6 |
8 |
| 0 |
2 |
4 |
6 |
6 |
8 |
由状态转移方程可以看出，f[i][j]都是来自于第i-1层的数据，这时就可以使用可以利用一层空间进行状态的记录，我们只需要从大到小的枚举， 那么$f[j - v[i]]$的状态就是$f[i - 1][j - v[i]]$的状态。
伪代码如下：
1
2
3
4
5
|
for i <- 1 to n:
for j <- v to v[i]:
f[j] = max(f[j], f[j - v[i] + w[i])
|
因为使用一维状态，那么f[j] = f[i - 1][j]保持着上次的数据，这时就只需要枚举到v[i]。但是在二维背包中，f[i][j]默认是0，每层的背包都需要跟新，所以背包容量j从0开始枚举到m。
具体Python代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| N = 1010
dp, v, w = [0]*N, [0]*N, [0]*N
def main():
n, m = map(int, input().split())
for i in range(1, n + 1):
v[i], w[i] = map(int, input().split())
for i in range(1, n + 1):
for j in range(m, v[i] - 1, -1):
dp[j] = max(dp[j], dp[j - v[i]] + w[i])
print(dp[m])
main()
|