摘要
Title: 4. 多重背包问题 I
Tag: 多重背包
Memory Limit: 64 MB
Time Limit: 1000 ms

4. 多重背包问题 I

题意

有 N 种物品和一个容量是 V 的背包。
第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。
0<N,V≤100
0<vi,wi,si≤100
思路

多重背包：每件物品最多用 $s_i$ 件

朴素01背包： $f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i])$
朴素完全背包： $f[i][j] = max(f[i - 1][j - v[i] * k] + w[i] * k)$ $k = 0, 1, 2, ...$
优化后的完全背包： $f[i][j] = max(f[i - 1][j], f[i][j - v[i]] + w[i])$
优化空间的完全背包和01背包： $f[j] = max(f[j], f[j - v[i]] + w[i])$
朴素多重背包： $f[i][j] = max(f[i - 1][j - v[i] * k] + w[i] * k)$ $k = 0, 1, 2, ... s[i]$
优化空间的多重背包： $f[j] = max(f[j], f[j - v[i] * k] + w[i] * k)$ $k = 0, 1, 2, ... s[i]$

相比朴素完全背包，有了取件的限制

代码

朴素版本

'''
Author: NEFU AB-IN
Date: 2022-03-06 11:58:08
FilePath: \ACM\Acwing\4.py
LastEditTime: 2022-03-06 12:06:39
'''
n, m = map(int, input().split())

N = 110
v, w, s = [0] * N, [0] * N, [0] * N
dp = [[0] * N for _ in range(N)]

for i in range(1, n + 1):
    v[i], w[i], s[i] = map(int, input().split())

for i in range(1, n + 1):
    for j in range(0, m + 1): #体积从0开始枚举
        k = 0
        while k <= s[i] and k * v[i] <= j:
            dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i] * k] + w[i] * k)
            k += 1

print(dp[n][m])

按01背包思想，将dp数组降为一维

'''
Author: NEFU AB-IN
Date: 2023-03-31 20:53:43
FilePath: \Acwing\4\4.1.py
LastEditTime: 2023-03-31 20:55:59
'''
# import
import sys, math
from collections import Counter, deque
from heapq import heappop, heappush
from bisect import bisect_left, bisect_right

# Final
N = int(1e2 + 10)
INF = int(2e9)

# Define
sys.setrecursionlimit(INF)
read = lambda: map(int, input().split())

# —————————————————————Division line ————————————————————————————————————————

n, m = read()
v, w, s = [0] * N, [0] * N, [0] * N
dp = [0] * N

for i in range(1, n + 1):
    v[i], w[i], s[i] = read()

for i in range(1, n + 1):
    for j in range(m, -1, -1):
        k = 0
        while k <= s[i] and k * v[i] <= j:
            dp[j] = max(dp[j], dp[j - v[i] * k] + w[i] * k)
            k += 1

print(dp[m])

4. 多重背包问题 I

题意

思路

代码