题目描述
有 N 种物品和一个容量是 V 的背包。
第 i 种物品最多有 si 件,每件体积是 vi,价值是 wi。
求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。
输出最大价值。
输入格式
第一行两个整数,N,V,用空格隔开,分别表示物品种数和背包容积。
接下来有 N 行,每行三个整数 vi,wi,si,用空格隔开,分别表示第 i 种物品的体积、价值和数量。
输出格式
输出一个整数,表示最大价值。
数据范围
0<N≤1000
0<V≤2000
0<vi,wi,si≤2000
提示:
本题考查多重背包的二进制优化方法。
样例
输入样例
4 5
1 2 3
2 4 1
3 4 3
4 5 2
输出样例:
10
算法1
(动态规划) $O(nvlogs)$
首先这个题目与完全背包的不同点在于完全背包限制选法的是背包的容积,而多重背包限制选法的可能是物品的数量s,所以我们不能够用完全背包的状态转移方程去描述它。而如果依次枚举每个物品选择的数量带入完全背包的状态转移方程的话有可能会超时,所以我们可以用一种二进制表述的方法去优化它。每一位二进制就代表一个物品,这样就可以把原先的一个物品分为多个物品,但是分完后的每个物品最多只能选一次。基于这种分法,我们有几点需要注意:
1.因为我们必须保证分完后的每种物品都能选或不选,并且所有选法均不超过物品原本数量s,所以我们所有的二进制数的总合不能超过s
2.每种物品不能够选择多次
基于以上两点,所以最后的s可能会有剩余。举个例子:假设一个物品有100件,按照上面的描述,我们就可以将其分为1/2/4/6/8/16/32/37这8种物品,每种物品最多只能选一次(相当于s变为了1),这样就成功转化为了01背包问题。为什么不能再分出64?这样的话64 + 32 + 8 = 104 > 100了,这样就不满足了
Python3 代码
n , m = map(int, input().split())
v = [0] * 12000
w = [0] * 12000
dp = [0] * 2010
cnt = 0
for i in range(1, n + 1):
a , b , s = map(int, input().split())
k = 1
while k <= s:
cnt += 1
v[cnt] = k * a
w[cnt] = k * b
s -= k
k = k * 2
if s > 0:
cnt += 1
v[cnt] = s * a
w[cnt] = s * b
n = cnt
for i in range(1, n + 1):
for j in range(m, v[i] - 1, -1):
dp[j] = max(dp[j], dp[j - v[i]] + w[i])
print(dp[m])