【洛谷P1858】多人背包
多人背包
题目描述：
DD 和好朋友们要去爬山啦！他们一共有 (K) 个人，每个人都会背一个包。这些包的容量是相同的，都是 (V)。可以装进背包里的一共有 (N) 种物品，每种物品都有给定的体积和价值。在 DD 看来，合理的背包安排方案是这样的：
- 每个人背包里装的物品的总体积恰等于包的容量。
- 每个包里的每种物品最多只有一件，但两个不同的包中可以存在相同的物品。
- 任意两个人，他们包里的物品清单不能完全相同。
在满足以上要求的前提下，所有包里的所有物品的总价值最大是多少呢？
输入格式：
第一行有三个整数：(K)、(V)、(N)。
第二行开始的 (N) 行，每行有两个整数，分别代表这件物品的体积和价值。
输出格式：
只需输出一个整数，即在满足以上要求的前提下所有物品的总价值的最大值。
样例输入：
2 10 5 3 12 7 20 2 4 5 6 1 1
样例输出：
57
数据范围：
总人数 (K<=50)。
每个背包的容量 (V<=5000)。
物品种类数 (N<=200)。
其它正整数都不超过 5000。
输入数据保证存在满足要求的方案。
时间限制：
1S
空间限制：
128M
提示：
remove!!!
题解
多人背包？那不就是背包问题吗？
看题目好像还是01背包。
有(K)个人，每个人的背包装的东西不能相同，那么不就是前(K)大01背包吗？
我们在原来的01背包上增加一维来维护前(K)大就行了。
(dp[i][j])表示体积为(i)时第(j)大的价值是多少。
转移的时候要注意一下，要用类似于归并排序合并时的方法转移。（具体如何实现看代码）
int u1=1,u2=1;
while(u1+u2-1<=k && (dp[j+a][u1]!=-1 || dp[j][u2]!=-1)){
if(dp[j+a][u1]!=-1 && (dp[j][u2]==-1 || dp[j+a][u1]>dp[j][u2]+b)){us[u1+u2-1]=dp[j+a][u1];u1++;}
else{us[u1+u2-1]=dp[j][u2]+b;u2++;}
}
for(int o=1;o<=u1+u2-2;o++)
dp[j+a][o]=us[o];//更新dp中的值
因为只求前(k)大的和，所以(dp)过程中只用维护前(k)大就行了。
注意最后更新时循环是1到(u1+u2-2)，因为前面循环结束时(u1)或者(u2)会多加一次。
要注意这里不能用1到(k)，因为前(k)个可能不一定全部被更新过，如果(dp[j+a][k])没有被更新过，就用它去更新下一个，就会出bug。
上代码：
#include<bits/stdc++.h>
using namespace std;
int k,v,n;
int a,b;
int dp[5009][59];
int us[59];
int ans;
int main(){
scanf("%d%d%d",&k,&v,&n);
memset(dp,-1,sizeof(dp));
dp[0][1]=0;
for(int i=1;i<=n;i++){
scanf("%d%d",&a,&b);
for(int j=v-a;j>=0;j--){
if(dp[j][1]!=-1){//没有这个判断对于结果没有影响，只是用来节省一点点时间
int u1=1,u2=1;
while(u1+u2-1<=k && (dp[j+a][u1]!=-1 || dp[j][u2]!=-1)){
if(dp[j+a][u1]!=-1 && (dp[j][u2]==-1 || dp[j+a][u1]>dp[j][u2]+b)){
us[u1+u2-1]=dp[j+a][u1];u1++;
}else{us[u1+u2-1]=dp[j][u2]+b;u2++;}
}
for(int o=1;o<=u1+u2-2;o++)
dp[j+a][o]=us[o];
}
}
}
for(int j=1;j<=k;j++)
ans+=dp[v][j];
printf("%d",ans);
return 0;
}