n, v = [int(x) for x in input().split(" ")]
f = [[0] * (n + 1 + v) for _ in range(n + 1 + v)]
ws = [0] * (n + 1)
vs = [0] * (n + 1)
for i in range(1, n + 1):
vs[i], ws[i] = [int(x) for x in input().split(" ")]
for i in range(1, n + 1):
for j in range(0, v + 1):
f[i][j] = f[i - 1][j]
if j >= vs[i]:
f[i][j] = max(f[i][j], f[i - 1][j - vs[i]] + ws[i])
print(f[n][v])
n, v = [int(x) for x in input().split(" ")]
f = [0] * (n + 1 + v)
ws = [0] * (n + 1)
vs = [0] * (n + 1)
for i in range(1, n + 1):
vs[i], ws[i] = [int(x) for x in input().split(" ")]
for i in range(1, n + 1):
for j in range(v, vs[i] - 1, -1):
f[j] = max(f[j], f[j - vs[i]] + ws[i])
print(f[v])
有 N 种物品和一个容量是 V的背包，每种物品都有无限件可用。
第 i种物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。 输出最大价值。
输入格式
第一行两个整数N，V，用空格隔开，分别表示物品种数和背包容积。
接下来有 N行，每行两个整数 vi，wi，用空格隔开，分别表示第 ii 种物品的体积和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤1000 0<vi,wi≤1000
输入样例
4 5
1 2
2 4
3 4
4 5
输出样例：
10
n, v = [int(x) for x in input().split(" ")]
f = [[0] * (n + 1 + v) for _ in range(n + 1 + v)]
vi = [0] * (n + 1)
wi = [0] * (n + 1)
for i in range(1, n + 1):
vi[i], wi[i] = [int(x) for x in input().split(" ")]
# 从前i可物品中选
for i in range(1, n + 1):
for j in range(v + 1):
# f[i][j] = f[i - 1][j]
for k in range(j + 1):
if j < vi[i] * k:
break
f[i][j] = max(f[i][j], f[i - 1][j - vi[i] * k] + wi[i] * k)
print(f[n][v])
# 注意数据加强后朴素做法已经不能过了
n, v = [int(x) for x in input().split(" ")]
f = [[0] * (n + 1 + v) for _ in range(n + 1 + v)]
vi = [0] * (n + 1)
wi = [0] * (n + 1)
for i in range(1, n + 1):
vi[i], wi[i] = [int(x) for x in input().split(" ")]
# 从前i可物品中选
for i in range(1, n + 1):
for j in range(v + 1):
f[i][j] = f[i - 1][j]
if j >= vi[i]:
f[i][j] = max(f[i][j], f[i][j - vi[i]] + wi[i])
print(f[n][v])
n, v = [int(x) for x in input().split(" ")]
f = [0] * (v + 1)
vi = [0] * (n + 1)
wi = [0] * (n + 1)
for i in range(1, n + 1):
vi[i], wi[i] = [int(x) for x in input().split(" ")]
# 从前i可物品中选
for i in range(1, n + 1):
for j in range(vi[i], v + 1):
f[j] = max(f[j], f[j - vi[i]] + wi[i])
print(f[v])
有 N 种物品和一个容量是 V 的背包。
第 i 种物品最多有 si件，每件体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。 输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。
接下来有 N 行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i种物品的体积、价值和数量。
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤100 0<vi,wi,si≤100
输入样例
4 5
1 2 3
2 4 1
3 4 3
4 5 2
输出样例：
10
n, v = [int(x) for x in input().split(" ")]
vi = [0] * (n + 1)
wi = [0] * (n + 1)
si = [0] * (n + 1)
f = [[0] * (n + 1 + v) for _ in range(n + 1 + v)]
for i in range(1, n + 1):
vi[i], wi[i], si[i] = [int(x) for x in input().split(" ")]
for i in range(1, n + 1):
for j in range(v + 1):
for k in range(si[i] + 1):
if j < vi[i] * k:
break
f[i][j] = max(f[i][j], f[i - 1][j - vi[i] * k] + wi[i] * k)
print(f[n][v])
数据范围
0<N≤1000 0<V≤2000 0<vi,wi,si≤2000
from math import log2
n, v = [int(x) for x in input().split(" ")]
xx = n * (int(log2(v)) + 1)
vi = [0] * xx
wi = [0] * xx
dp = [0] * (v + 1)
cnt = 0
for _ in range(n):
a, b, c = [int(x) for x in input().split(" ")]
k = 1
while c >= k:
cnt += 1
vi[cnt] = k * a
wi[cnt] = k * b
c -= k
k *= 2
if c > 0:
cnt += 1
vi[cnt] = c * a
wi[cnt] = c * b
for i in range(1, cnt + 1):
for j in range(v, -1, -1):
if j < vi[i]:
break
dp[j] = max(dp[j], dp[j - vi[i]] + wi[i])
print(dp[v])
n, m = [int(x) for x in input().split(" ")]
q = [[0, 0] for _ in range(m + 1)] # (pos, val)
dp = [0] * (m + 1)
for _ in range(n):
v, w, s = [int(x) for x in input().split(" ")]
for j in range(v):
hh, tt, stop = 0, 0, (m - j) // v
for k in range(stop + 1):
val = dp[k * v + j] - k * w
while hh < tt and val >= q[tt - 1][1]:
tt -= 1
q[tt][0] = k
q[tt][1] = val
tt += 1
if q[hh][0] < k - s:
hh += 1
dp[v * k + j] = q[hh][1] + k * w
print(dp[m])
有 N种物品和一个容量是 V 的背包。
物品一共有三类：
第一类物品只能用1次（01背包）；
第二类物品可以用无限次（完全背包）；
第三类物品最多只能用 si次（多重背包）；
每种体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。 输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。
接下来有 NN 行，每行三个整数 vi,wi,si用空格隔开，分别表示第 i 种物品的体积、价值和数量。
si=−1表示第 i 种物品只能用1次；
si=0 表示第 i 种物品可以用无限次；
si>0 表示第 i 种物品可以使用 si 次；
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤1000 0<vi,wi≤1000 −1≤si≤1000
输入样例
4 5
1 2 -1
2 4 1
3 4 0
4 5 2
输出样例：
8
from math import log2
n, m = [int(x) for x in input().split()]
f = [0] * (m + 1)
xx = n * (int(log2(m)) + 1)
a = [0] * xx
b = [0] * xx
c = [False] * xx # False: 完全背包，True 0-1背包
index = 0
for _ in range(n):
v, w, s = [int(x) for x in input().split()]
if s == 0:
a[index] = v
b[index] = w
index += 1
else:
if s == -1:
s = 1
k = 1
while k <= s:
a[index] = k * v
c[index] = True
b[index] = k * w
index += 1
s -= k
k <<= 1
if s:
a[index] = s * v
c[index] = True
b[index] = s * w
index += 1
for i in range(index):
if c[i]:
for j in range(m, a[i] - 1, -1):
f[j] = max(f[j], f[j - a[i]] + b[i])
else:
for j in range(a[i], m + 1):
f[j] = max(f[j], f[j - a[i]] + b[i])
print(f[m])
n, v, m = [int(x) for x in input().split()]
dp = [[0] * (m + 1) for _ in range(v + 1)]
for _ in range(n):
a, b, c = [int(x) for x in input().split()]
for j in range(v, a - 1, -1):
for k in range(m, b - 1, -1):
dp[j][k] = max(dp[j][k], dp[j - a][k - b] + c)
print(dp[v][m])
分组背包问题目前还没有看见有优化版本，多是朴素做法
有 N组物品和一个容量是 V 的背包。
每组物品有若干个，同一组内的物品最多只能选一个。 每件物品的体积是 v[i][j]，价值是 w[i][j]，其中 i 是组号，j 是组内编号。
求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式
第一行有两个整数 N，V，用空格隔开，分别表示物品组数和背包容量。
接下来有 NN 组数据：
每组数据第一行有一个整数 S[i]，表示第 i 个物品组的物品数量；
每组数据接下来有 Si 行，每行有两个整数v[i][j]w[i][j]，用空格隔开，分别表示第 i 个物品组的第 j 个物品的体积和价值；
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤100 0<S ≤ 100 0<v[i][j], w[i][j] ≤100
输入样例
3 5
2
1 2
2 4
1
3 4
1
4 5
输出样例：
8
n, v = [int(x) for x in input().split(" ")]
vi = [[0] * (n + 1 + v) for _ in range(n + 1)]
wi = [[0] * (n + 1 + v) for _ in range(n + 1)]
si = [0] * (n + 1)
f = [0] * (v + 1)
for i in range(1, n + 1):
si[i] = int(input())
for j in range(si[i]):
vi[i][j], wi[i][j] = [int(x) for x in input().split(" ")]
for i in range(1, n + 1):
for j in range(v, -1, -1):
for k in range(si[i]):
if vi[i][k] > j:
continue
f[j] = max(f[j], f[j - vi[i][k]] + wi[i][k])
print(f[v])
