头像

hhljhjhjk


访客:7530

离线:22小时前


活动打卡代码 AcWing 7. 混合背包问题

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])


活动打卡代码 AcWing 532. 货币系统

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)


活动打卡代码 AcWing 426. 开心的金明

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])


活动打卡代码 AcWing 1013. 机器分配

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)))


活动打卡代码 AcWing 1021. 货币系统

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])


活动打卡代码 AcWing 1023. 买书

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])


活动打卡代码 AcWing 1019. 庆功会

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):
        head, tail = 0, -1
        # d + k * vi <= v
        for k in range((v - d) // vi + 1):

            while head <= tail and q[head] <= k - si - 1:
                head += 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):
        head, tail = 0, -1
        # d + k * vi <= v
        for k in range((v - d) // vi + 1):

            while head <= tail and q[head] <= k - si - 1:
                head += 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])


活动打卡代码 AcWing 278. 数字组合

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)