盛日辉的博客
0%

蓝桥-小明的背包

发表于 分类于 ，

小明的背包2

题目

https://www.lanqiao.cn/problems/1175/learning/

代码1滚动数组（超时）

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
36
# 数量，容量
n, c = map(int, input().split())
# W = [0]
# V = [0]
# for _ in range(n):
#     w, v = map(int, input().split())
#     while w <= c:
#         W.append(w)
#         V.append(v)
#         w += w
#         v += v
# nn = len(W)
# dp = [0] * (c + 1)
#
# for i in range(1, nn ):
#     for j in range(c, W[i] - 1, -1):
#         dp[j] = max(dp[j], dp[j - W[i]] + V[i])
# print(dp[-1])


W = [0]
V = [0]
for _ in range(n):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)
dp = [0] * (c + 1)

for i in range(1, n):
    w = W[i]
    for j in range(c, w - 1, -1):
        k = 1
        while w * k <= j:
            dp[j] = max(dp[j], dp[j - w * k] + k * V[i])
            k += 1
print(dp[-1])

代码2（普通）

超时更多

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 数量，容量
n, c = map(int, input().split())
W = [0]
V = [0]
for _ in range(n):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)
dp = [[0] * (c + 1) for _ in range(n + 1)]

for i in range(1, n + 1):
    for j in range(1, c + 1):
        if i == 1:
            dp[i][j] = 0
        else:
            dp[i][j] = dp[i - 1][j]
        for k in range(0, j // W[i] + 1):
            dp[i][j] = max(dp[i][j], dp[i - 1][j - W[i] * k] + k * V[i])

print(dp[n][c])

代码3（某题解）

之前都有一个k循环在，但其实如果j循环是从小往大的，每一次取找j-w[i]的时候，就相当于k加上了1（多拿了一个w[i]）。

1
2
3
4
5
6
7
N, V = map(int, input().split())
dp = [0] * (V + 1)
for _ in range(N):
    w, v = map(int, input().split())
    for j in range(w, V + 1):
        dp[j] = max(dp[j], dp[j - w] + v)
print(dp[-1])