原题链接
-
朴素多重背包问题：
当外层循环到i时，dp[j]表示从前i种物品中选出若干个放入背包，体积之和为j时，价值之和最大值是多少
for (int i = 1; i <= n; ++ i) {
int v, w, s;
cin >> v >> w >> s;
for (int j = 0; j <= m; ++ j)
for (int k = 0; k <= s && k * v <= j; ++ k)
dp[i][j] = max(dp[i][j], dp[i - 1][j - k * v] + k * w);
}
理论：1 ~ N分为X类，每一类都是余数为1 ~ X的集合，那么这X类的并集还是1~N
-
优化成一维滚动数组：
dp[m] 表示容量为m的情况下，获得的最大价值，逆序循环m，在状态转移时，考虑选取第i个物品的个数k，针对每一类物品 i ，我们都更新一下 dp[m] .....dp[0] 的值，最后 dp[m] 就是一个全局最优值
dp[m] = max(dp[m], dp[m-v] + w, dp[m-2*v] + 2*w, dp[m-3*v] + 3*w, ...)
-
单调队列优化
接下来，我们把 dp[0] ......dp[m] 写成下面这种形式:
dp[0] , dp[v] , dp[2v], dp[3v], ... , dp[kv]
dp[1], dp[v+1], dp[2v+1], dp[3v+1], ... , dp[kv+1]
dp[2], dp[v+2], dp[2v+2], dp[3v+2], ... , dp[kv+2]
...
dp[j-1], dp[v+j-1], dp[2v+j-1], dp[3v+j-1], ... , dp[kv+j-1]
其中 0 < = （ j - 1 ） < v ，m = k * v + j - 1
所以，我们可以把 dp 数组分成 j 个类，每一类中的值，都是在同类之间转换得到的，
对于max{ dp[j-1], dp[v+j-1], dp[2v+j-1], dp[3v+j-1], ... , dp[kv+j-1] },可以通过一个单调队列来维护
把状态j按照除以Vi的余数分组，每一组分别进行计算，余0组，余1组....余Vi-1组，就是j个单调队列
以dp[j]为例，在维护一个单调队列中，当更新dp数组时
dp[j]=max(dp[j])
dp[j+v]=max(dp[j]+w,dp[j+v])
dp[j+2v]=max(dp[j]+2*w,dp[j+v]+w,dp[j+2v])
.....
发现这个队列中前面的数，每次都会增加一个 w ，所以需要做一些转换
dp[j]=max(dp[j])
dp[j+v]=max(dp[j],dp[j+v]-w)+w
dp[j+2v]=max(dp[j],dp[j+v]-w,dp[j+2v]-2w)+2w
.....
取max中的通项，每次入队时的值是 dp[j+kv] - kw，当前dp值减去k个w
-
维护单调队列
1）维护队列元素的个数，如果不能继续入队，弹出队头元素
2）分别考虑放和不放第i个物品（省去一维），择优
dp[i][k] = dp[i - 1][k]; // 不放物品i
if (hh <= tt)
dp[i][k] = max(dp[i][k], dp[i - 1][q[hh]] + (k - q[hh]) / v * w); // 放物品i
3）维护队列的单调递减，最大值放在队列头，降低到一维的时候，我们要用i-1时刻去更新，而顺序枚举时会导致旧的值被覆盖，所以每次更新最大值需要备份数组pre更新dp，因为dp[k]通过前面的pre[q[hh]]来更新最大值，窗口在pre数组上滑动，因此
dp[k]=窗口中的最大值+还能放入物品的价值
4）每次换另一种物品时用dp数组更新pre数组，因此迭代出的dp[m]就是最大值
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=20010;
int n,v;
int dp[N],q[N],g[N];
int main()
{
cin>>n>>v;
for(int i=0;i<n;i++)
{
int c,w,s;
cin>>c>>w>>s;//体积、价值和数量
memcpy(pre,dp,sizeof dp);//pre表示i-1时刻，dp数组为i时刻
for(int j=0;j<c;j++)//枚举余数，j个单调队列
{
int hh=0,tt=-1;//建立单调队列
for(int k=j;k<=v;k+=c)//枚举候选集合
{
if(hh<=tt&&k-q[hh]>s*c) hh++;//队列满了
if(hh<=tt) dp[k]=max(dp[k],pre[q[hh]]+(k-q[hh])/c*w);
//最大值在队列头部，pre[q[hh]]记载，加上还能放入物品的价值，取决策，放还是不放，更新dp数组的最大值
while(hh<=tt&&pre[q[tt]]-(q[tt]-j)/c*w<=pre[k]-(k-j)/c*w) tt--;
//维护单调队列递减，新加入的元素满足上面推导的通项公式
q[++tt]=k;//插入队列
}
}
}
cout<<dp[v]<<endl;
return 0;
}
网友评论