n,V = map(int,input().strip().split(' ')) w = [0] p = [0] dp = [[0]*(V+1) for i inrange(n+1)] for i inrange(n): a,b = map(int,input().strip().split(' ')) w.append(a) p.append(b)
for i inrange(1,n + 1): for j inrange(V + 1): dp[i][j] = dp[i - 1][j] if j >= w[i]: dp[i][j] = max(dp[i -1][j],dp[i - 1][j - w[i]] + p[i])
print(dp[n][V])
空间优化
除此之外,还可以对空间进行优化:
先来看看转移方程
对于更新物品 i 的值只与物品 i - 1 有关,可以用一个滚动数组进行优化。
对于容量 j 只与上一层的容量 j 和 j - w 有关,也就意味着 小容量可以影响大容量的值,即如果先更新小容量 j - w ,那么上一层容量为 j - w 的最大价值就会丢失。所以需要先更新大的值在更新小的值。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
n,V = map(int,input().strip().split(' ')) w = [0] p = [0] dp = [0] * (V+ 1) for i inrange(n): a,b = map(int,input().strip().split(' ')) w.append(a) p.append(b)
for i inrange(1,n + 1): for j inrange(V , -1 , -1): dp[j] = dp[j] if j >= w[i]: dp[j] = max(dp[j],dp[j - w[i]] + p[i])
print(dp[V])
完全背包
有 n 种物品和一个大小为V的背包。
其中第i种物品的体积为wi,价值为pi,每种物品有无数个,
现将一些物品放入背包,在不超过背包容量的情况下,获得物品价值总和最大。
与 01 背包的差别在于物品有无数个
方法
定义dp[i][j] : 表示第i件物品,在j的容量下能获得的最大价值。
对于第 i 个物品我们有很多选择,要么不选,要么选 1 ,2 ,3 ,… , k , … 个,划分集合:
可以发现两者非常相近,dp[i][j -w] + p 和 上面的数据一样,将这些部分替换掉就可以得到
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
n,V = map(int,input().strip().split(' ')) w = [0] p = [0] dp = [[0]*(V+1) for i inrange(n+1)] for i inrange(n): a,b = map(int,input().strip().split(' ')) w.append(a) p.append(b)
for i inrange(1,n + 1): for j inrange(V + 1): dp[i][j] = dp[i - 1][j] if j >= w[i]: dp[i][j] = max(dp[i -1][j],dp[i][j - w[i]] + p[i])
wAndp = [] for i inrange(n): num = 1 while s[i] > 0: if s[i] - num >= 0: wAndp.append([num*w[i],num*p[i]]) s[i] -= num else: wAndp.append([s[i]*w[i],s[i]*p[i]]) break num *= 2
n,V = map(int,input().strip().split(' ')) w = [] p = [] s = [] dp = [0] * (V+1)
for i inrange(n): a,b,c = map(int,input().strip().split()) w.append(a) p.append(b) s.append(c)
wAndp = [] for i inrange(n): num = 1 while s[i] > 0: if s[i] - num >= 0: wAndp.append([num*w[i],num*p[i]]) s[i] -= num else: wAndp.append([s[i]*w[i],s[i]*p[i]]) break num *= 2
for i inrange(len(wAndp)): for j inrange(V,-1,-1): dp[j] = dp[j] if j >= wAndp[i][0]: dp[j] = max(dp[j],dp[j - wAndp[i][0]] + wAndp[i][1])
for k inrange(j,V + 1,w[i]): start,end= 0,-1 if(start <= end and k - queue[start] > s[i] * w[i]): start += 1 if start <= end: dp[k] = max(dp[k],old_dp[queue[start]] + (k - queue[start])//w[i] * p[i]) while start <= end and old_dp[queue[end]] - (queue[end] - j)//w[i]*p[i] <= old_dp[k] - (k - j)//w[i]*p[i]: end -= 1 end += 1 queue[end] = k
关于上面的变量解释
queue
start
end
k
w
p
j
dp
dp_old
队列
队头
队尾
当前位置
物品体积
物品价值
同余数
当前轮的数据
上一轮的数据
对于end >= start是队尾一定要在队头后面
1 2 3 4 5 6 7 8
graph LR; subgraph queue 1[null] --> 2[null] --> 3[null] --> 4[null] end subgraph N start -.-> 1 e[end] -.-> -1 end
开始的时候end指向的是一个空位置,当有数据加入时end++ 在将数据填入queue
,即:
1 2 3 4 5 6 7 8
graph LR; subgraph queue 1[1] --> 2[null] --> 3[null] --> 4[null] end subgraph N start -.-> 1 e[end] -.-> 1 end
1 2 3 4 5 6 7 8
graph LR; subgraph queue 1[1] --> 2[2] --> 3[null] --> 4[null] end subgraph N start -.-> 1 e[end] -.-> 2 end
1 2 3 4 5 6 7 8
graph LR; subgraph queue 1[1] --> 2[2] --> 3[3] --> 4[null] end subgraph N start -.-> 1 e[end] -.-> 3 end
当有数据移除是start++
1 2 3 4 5 6 7 8
graph LR; subgraph queue 1[1] --> 2[2] --> 3[3] --> 4[null] end subgraph N start -.-> 2 e[end] -.-> 3 end
n , V = map(int,input().strip().split()) w = [] p = [] s = [] dp = [0]*(V + 1) queue = [0]*(V + 1)
for i inrange(n): a,b,c = map(int, input().strip().split()) w.append(a) p.append(b) s.append(c)
for i inrange(n): for j inrange(w[i]): old_dp = dp.copy() for k inrange(j,V + 1,w[i]): start,end= 0,-1 if(start <= end and k - queue[start] > s[i] * w[i]): start += 1 if start <= end: dp[k] = max(dp[k],old_dp[queue[start]] + (k - queue[start])//w[i] * p[i]) while start <= end and old_dp[queue[end]] - (queue[end] - j)//w[i]*p[i] <= old_dp[k] - (k - j)//w[i]*p[i]: end -= 1 end += 1 queue[end] = k