hhljhjhjk

hhljhjhjk
7个月前
n, v = map(int, input().split())

f = [0 for _ in range(v + 1)]
for _ in range(n):
vi, wi, si = map(int, input().split())
if si == 0: # 完全背包
for j in range(vi, v + 1):
f[j] = max(f[j], f[j - vi] + wi)
elif si == -1: # 01背包
for j in range(v, vi - 1, -1):
f[j] = max(f[j], f[j - vi] + wi)
else: # 多重背包 二进制优化
k = 1
while k <= si:
for j in range(v, vi * k - 1, -1):
f[j] = max(f[j], f[j - k * vi] + k * wi)
si -= k
if si > 0:
for j in range(v, vi * s - 1, -1):
f[j] = max(f[j], f[j - si * vi] + si * wi)
print(f[v])


hhljhjhjk
7个月前
# 可通过反正法证明 b是a的子集

t = int(input())
for _ in range(t):
n = int(input())
a = [int(x) for x in input().split()]

a.sort()
f = [0 for _ in range(a[-1] + 1)]
f[0] = 1

res = 0
for c in a:
if f[c] == 0:
res += 1
for j in range(c, a[-1] + 1):
f[j] += f[j - c]

print(res)


hhljhjhjk
7个月前
# 01背包
n, m = map(int, input().split())

f = [0 for _ in range(n + 1)]
for _ in range(m):
v, p = map(int, input().split())
w = v * p
for j in range(n, v - 1, -1):
f[j] = max(f[j], f[j - v] + w)
print(f[n])


hhljhjhjk
7个月前
# 用二进制枚举所有情况

n, m = map(int, input().split())
master, servent = [0 for _ in range(m + 1)], [[] for _ in range(m + 1)]
for i in range(1, m + 1):
v, p, q = map(int, input().split())
if q == 0:
master[i] = [v, v * p]
else:
servent[q].append([v, v * p])

f = [0 for _ in range(n + 1)]
for i in range(1, m + 1):
if master[i] == 0:
continue

for j in range(n, -1, -1):
# 二进制枚举所有情况
for k in range(1 << len(servent[i])):
v, w = master[i][0], master[i][1]
for u in range(len(servent[i])):
if k >> u & 1:
v += servent[i][u][0]
w += servent[i][u][1]
if j >= v:
f[j] = max(f[j], f[j - v] + w)
print(f[n])


hhljhjhjk
7个月前
# DP解法
# 每个公司视为一组，组内物品为：当分配0到M台时对应的盈利
# 然后当作分组背包来做，每一组选一个物品

n, v = map(int, input().split())
alls = []

for _ in range(n):
alls.append([0] + [int(x) for x in input().split()])

f = [[0 for _ in range(v + 1)] for _ in range(n + 1)]
for i in range(1, n + 1):
single = alls[i - 1]
for j in range(v + 1):
for k in range(v + 1):
if k <= j:
f[i][j] = max(f[i][j], f[i - 1][j - k] + single[k])
print(f[n][v])

# 从后往前遍历求方案
res = []
remain = v
for i in range(n, 0, -1):
single = alls[i - 1]
for k in range(v + 1):
if f[i][remain] == f[i - 1][remain - k] + single[k]:
remain -= k
res.append(k)
break
res.reverse()
for i in range(1, n + 1):
print(i, res[i - 1])

# dfs暴搜
def dfs(u, remain, count):
global res, path, n, matrix, maxv

if u == n:
if count > maxv:
maxv = count
res = path.copy()
return

for i in range(remain + 1):
path.append(i)
dfs(u + 1, remain - i, count + matrix[u][i])
path.pop()

n, m = map(int, input().split())
matrix = []
for _ in range(n):
matrix.append([0] + [int(x) for x in input().split()])

res = []
path = []
maxv = 0

dfs(0, m, 0)

print(maxv)
for i, c in enumerate(res):
print(i + 1, c)


hhljhjhjk
7个月前
n, v = map(int, input().split())
vs, ws = [0], [0]
for _ in range(n):
vi, wi = map(int, input().split())
vs.append(vi)
ws.append(wi)

# 从后往前求最大值
f = [[0 for _ in range(v + 1)] for _ in range(n + 2)]
for i in range(n, 0, -1):
for j in range(v + 1):
f[i][j] = f[i + 1][j]
if vs[i] <= j:
f[i][j] = max(f[i][j], f[i + 1][j - vs[i]] + ws[i])

# 从前往后遍历贪心求方案
res = []
remainv = v
for i in range(1, n + 1):
if remainv >= vs[i] and f[i][remainv] == f[i + 1][remainv - vs[i]] + ws[i]:
res.append(i)
remainv -= vs[i]
print(' '.join(map(str, res)))


hhljhjhjk
7个月前
n, v = map(int, input().split())

f = [0 for _ in range(v + 1)]
f[0] = 1

for _ in range(n):
vi = int(input())
for j in range(vi, v + 1):
f[j] += f[j - vi]
print(f[v])


hhljhjhjk
7个月前
v = int(input())
vs = [10, 20, 50, 100]

f = [0 for _ in range(v + 1)]
f[0] = 1

for vi in vs:
for j in range(vi, v + 1):
f[j] += f[j - vi]
print(f[v])


hhljhjhjk
7个月前
# 朴素多重背包
n, v = map(int, input().split())
f = [[0 for _ in range(v + 1)] for _ in range(n + 1)]
for i in range(1, n + 1):
vi, wi, si = map(int, input().split())
for j in range(v + 1):
for k in range(min(j // vi, si) + 1):
f[i][j] = max(f[i][j], f[i - 1][j - k * vi] + k * wi)
print(f[n][v])

# 滚动数组优化空间复杂度
n, v = map(int, input().split())
f = [0 for _ in range(v + 1)]

for _ in range(n):
vi, wi, si = map(int, input().split())
for j in range(v, vi - 1, -1):
for k in range(min(j // vi, si) + 1):
f[j] = max(f[j], f[j - k * vi] + k * wi)
print(f[v])

# 二进制优化 + 01背包
n, v = map(int, input().split())

vs, ws = [], []
for _ in range(n):
vi, wi, si = map(int, input().split())

k = 1
while k <= si:
vs.append(k * vi)
ws.append(k * wi)

si -= k
k *= 2

if si:
vs.append(si * vi)
ws.append(si * wi)

m = len(vs)
f = [0 for _ in range(v + 1)]
for i in range(m):
vi, wi = vs[i], ws[i]
for j in range(v, vi - 1, -1):
f[j] = max(f[j], f[j - vi] + wi)
print(f[v])

# 单调队列优化
n, v = map(int, input().split())

f = [[0 for _ in range(v + 1)] for _ in range(n + 1)]
q = [0 for _ in range(v + 1)]
for i in range(1, n + 1):
vi, wi, si = map(int, input().split())
for d in range(vi):
# d + k * vi <= v
for k in range((v - d) // vi + 1):

while head <= tail and q[head] <= k - si - 1:
while head <= tail and f[i - 1][d + q[tail] * vi] - q[tail] * wi <= f[i - 1][d + k * vi] - k * wi:
tail -= 1

q[tail + 1] = k
tail += 1

f[i][d + k * vi] = f[i - 1][d + q[head] * vi] - q[head] * wi + k * wi
print(f[n][v])

# 单调队列优化 + 滚动数组优化
n, v = map(int, input().split())

# f = [[0 for _ in range(v + 1)] for _ in range(n + 1)]
f = [0 for _ in range(v + 1)]

q = [0 for _ in range(v + 1)]
for i in range(1, n + 1):
vi, wi, si = map(int, input().split())

g = f.copy()
for d in range(vi):
# d + k * vi <= v
for k in range((v - d) // vi + 1):

while head <= tail and q[head] <= k - si - 1:
while head <= tail and g[d + q[tail] * vi] - q[tail] * wi <= g[d + k * vi] - k * wi:
tail -= 1

q[tail + 1] = k
tail += 1

f[d + k * vi] = g[d + q[head] * vi] - q[head] * wi + k * wi
print(f[v])


hhljhjhjk
7个月前
# DP f[i][j]表示用前i个数，正好凑成和为j的组合数量
n, m = map(int, input().split())
nums = [int(x) for x in input().split()]

f = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
f[0][0] = 1

for i in range(1, n + 1):
for j in range(m + 1):
f[i][j] = f[i - 1][j]
if nums[i - 1] <= j:
f[i][j] += f[i - 1][j - nums[i - 1]]
print(f[n][m])

# 滚动数组优化
n, m = map(int, input().split())
nums = [int(x) for x in input().split()]

f = [0 for _ in range(m + 1)]
f[0] = 1

for num in nums:
for j in range(m, num - 1, -1):
f[j] += f[j - num]
print(f[m])

# dfs
def dfs(u, start, remain):
global res, state, nums, n

if remain == 0:
res += 1
return

if remain < 0 or u == n:
return

for i in range(start, n):
dfs(u + 1, i + 1, remain - nums[i])

n, m = map(int, input().split())
nums = [int(x) for x in input().split()]

nums.sort()
res = 0
state = set()

dfs(0, 0, m)
print(res)