# # Backpack problem
# # 01 Backpack
# ## Memorized search
from collections import Counter, defaultdict
from typing import List
# Recursive optimization
n, m = map(int, input().split())
a = []
for _ in range(n):
v, w = map(int, input().split())
a.append((v, w))
f = [0] * (1 + m)
# v,w volume, value
for v, w in a:
for j in range(m, v - 1, -1):
f[j] = max(f[j], f[j - v] + w)
print(f[-1])
# Complete backpack (unlimited options)
n, m = map(int, input().split())
a = []
for _ in range(n):
a.append(list(map(int, input().split())))
f = [0] * (m + 1)
for v, w in a:
# The difference from the 01 backpack is that this is a positive order traversal j, because f[i][j] is transferred from f[i][j - v]
for j in range(v, m + 1):
f[j] = max(f[j], f[j - v] + w)
print(f[-1])
# Find the maximum value of multiple backpacks
n, m = map(int, input().split())
a = []
for _ in range(n):
a.append(list(map(int, input().split())))
# Find the maximum value of multiple backpacks-simple conversion into 01 backpack to solve
f = [0] * (m + 1)
for v, w, s in a:
for j in range(m, v - 1, -1):
for k in range(s + 1):
if k * v > j:
break
f[j] = max(f[j], f[j - k * v] + k * w)
print(f[-1])
# Find the maximum value of multiple backpacks-binary optimization
n, m = map(int, input().split())
a = []
for _ in range(n):
v, w, s = map(int, input().split())
#Binary split
i=1
while i <= s:
a.append((v * i, w * i))
s -= i
i <<= 1
if s:
a.append((s * v, s * w))
f = [0] * (m + 1)
for v, w in a:
for j in range(m, v - 1, -1):
f[j] = max(f[j - v] + w, f[j])
print(f[-1])
# Find the maximum value of multiple backpacks - monotonic queue optimization
n, m = map(int, input().split())
a = []
for _ in range(n):
a.append(list(map(int, input().split())))
f = [0] * (m + 1)
q = [0] * (m + 1)
for v, w, s in a:
g = f[:]
for j in range(v): # Congruent with v in a monotonic queue, the value of the monotonic queue elements decreases
hh, tt = 0, -1
for k in range(j, m + 1, v): # Slide v each time
# f[k] = g[k]
if hh <= tt and k - s * v > q[hh]: # If k/v - q[0] > s, it means more than s v have been slid
hh + = 1
if hh <= tt: # update f
f[k] = max(f[k], g[q[hh]] + (k - q[hh]) // v * w) # Transfer from the maximum value (head of the team) and install k-q[0 ] items
while hh <= tt and g[q[tt]] - (q[tt] - j) // v * w <= g[k] - (k - j) // v * w:
# while hh <= tt and g[q[tt]] + (k - q[tt]) // v * w <= g[k]:
tt -= 1
tt + = 1
q[tt] = k
print(f[-1])
# Find the number of solutions for multiple backpacks
def countSubMultisets(self, nums: List[int], l: int, r: int) -> int:
MOD = 10 ** 9 + 7
total = sum(nums)
if l > total:
return 0
m = min(r, total)
cnt = Counter(nums)
f = [cnt[0] + 1] + [0] * m # f[i] represents the number of solutions with a volume of exactly i, and the volumes of 0 are grouped together
del cnt[0]
for v, s in cnt.items():
g = f[:]
for j in range(v, m + 1):
g[j] + = g[j - v]
if j >= (s + 1) * v:
g[j] -= f[j - (s + 1) * v]
g[j] %= MOD
f = g
return sum(f[l:]) % MOD
# Mixed backpack problem
# There are N items and a backpack with a capacity of V.
# There are three categories of items:
# The first type of item can only be used once (01 backpack);
# The second type of items can be used unlimited times (complete backpack);
# The third type of items can only be used a maximum of si times (multiple backpacks);
# Each volume is vi and the value is wi
# Find out which items should be put into the backpack so that the total volume of the items does not exceed the backpack capacity and the total value is the largest.
# Output the maximum value.
n, m = map(int, input().split())
a = []
for _ in range(n):
v, w, s = map(int, input().split())
if s == -1:
#01 Backpack
a.append((-1, v, w))
elif s == 0:
#completebackpack
a.append((0, v, w))
else:
# Multiple backpacks to 01 backpacks
k=1
while k <= s:
a.append((-1, v * k, w * k))
s -= k
k <<= 1
if s:
a.append((-1, v * s, w * s))
f = [0] * (m + 1)
for t, v, w in a:
if t == -1:
# 01 Backpack
for j in range(m, v - 1, -1):
f[j] = max(f[j], f[j - v] + w)
else:
#completebackpack
for j in range(v, m + 1):
f[j] = max(f[j], f[j - v] + w)
print(f[-1])
# 2D Cost Backpack
# There are N items and a backpack with a capacity V. The maximum weight the backpack can bear is M
# Each item can only be used once. Volume is vi, weight is mi, value is wi
# Find out which items should be packed into the backpack so that the total volume of the items does not exceed the capacity of the backpack, the total weight does not exceed the maximum weight that the backpack can bear, and the total value is the largest.
# Output the maximum value.
N, V, M = map(int, input().split())
a = []
for _ in range(N):
v, m, w = map(int, input().split())
a.append((v, m, w))
f = [[0] * (M + 1) for _ in range(V + 1)]
for v, m, w in a:
for j in range(V, v - 1, -1):
for k in range(M, m - 1, -1):
f[j][k] = max(f[j][k], f[j - v][k - m] + w)
print(f[-1][-1])
#Group backpack
# There are N sets of items and a backpack with a capacity of V.
# There are several items in each group, and only one item in the same group can be selected at most.
# The volume of each item is vij, and the value is wij, where i is the group number and j is the number within the group.
# Find out which items should be put into the backpack so that the total volume of the items does not exceed the backpack capacity and the total value is maximum.
# Output the maximum value.
N, V = map(int, input().split())
a = []
for _ in range(N):
b = []
for _ in range(int(input())):
b.append(list(map(int, input().split())))
a.append(b)
# Memoized search
# from functools import lru_cache
# @lru_cache(None)
# def dfs(i, V):
# if i < 0:
# return 0
# ans = dfs(i - 1, V)
# for v, w in a[i]:
# if v <= V:
# ans = max(ans, dfs(i - 1, V - v) + w)
# return ans
# print(dfs(N - 1, V))
# 2D
# f = [[0]*(V + 1) for _ in range(N + 1)]
# for i in range(1,N + 1):
# for j in range(1,V + 1):
# f[i][j] = f[i - 1][j]
# for k,(v,w) in enumerate(a[i - 1]):
# if v <= j:
# f[i][j] = max(f[i][j],f[i - 1][j - v] + w)
# print(f[-1][-1])
# One-dimensional
f = [0] * (V + 1)
for i in range(1, N + 1):
for j in range(V, 0, -1):
for k, (v, w) in enumerate(a[i - 1]):
if v <= j:
f[j] = max(f[j], f[j - v] + w)
print(f[-1])
# Backpack problem with dependencies
N, V = map(int, input().split())
from collections import defaultdict
g = defaultdict(list)
a = [-1]
for i in range(1,N + 1):
v, w, p = map(int, input().split())
if p == -1:
root=i
else:
g[p].append(i)
a.append((v, w, p))
f = [[0]*(V + 1) for _ in range(N + 1)]
def dfs(u):
v, w, p = a[u]
for i in range(v,V + 1):
f[u][i] = w
for son in g[u]:
dfs(son)
for j in range(V, v - 1, -1):
for k in range(j - v + 1):
f[u][j] = max(f[u][j], f[u][j - k] + f[son][k])
dfs(root)
print(f[root][V])
# 01 Find the number of solutions for a backpack
n, m = map(int, input().split())
a = []
for _ in range(n):
v, w = map(int, input().split())
a.append((v, w))
MOD = 10**9 + 7
f = [0] * (1 + m)
c = [1] * (1 + m)
# v,w volume, value
for v, w in a:
for j in range(m, v - 1, -1):
if f[j - v] + w > f[j]:
f[j] = f[j - v] + w
c[j] = c[j - v]
elif f[j - v] + w == f[j]:
c[j] + = c[j - v]
c[j] %= MOD
print(c[-1])
# 01 Backpack looking for specific solutions
n, m = map(int, input().split())
a = []
for _ in range(n):
v, w = map(int, input().split())
a.append((v, w))
f = [[0] * (1 + m) for _ in range(2 + n)]
p = [[0]*(1 + m) for _ in range(1 + n)]
for i in range(n,0,-1): # Take items in reverse order
v,w = a[i - 1]
for j in range(m + 1):
f[i][j] = f[i + 1][j]
p[i][j] = j
if j >= v:
f[i][j] = max(f[i][j],f[i + 1][j - v] + w)
if j >= v and f[i + 1][j - v] + w == f[i][j]:
p[i][j] = j - v
j=m
ans = []
for i in range(1,n + 1):
if p[i][j] < j:
ans.append(str(i))
j = p[i][j]
print(' '.join(ans))
The knowledge points of the article match the official knowledge files, and you can further learn related knowledge. Algorithm skill tree Home page Overview 56740 people are learning the system