题目链接

多人背包

题目描述:

DD 和好朋友们要去爬山啦!他们一共有 $K$ 个人,每个人都会背一个包。这些包的容量是相同的,都是 $V$。可以装进背包里的一共有 $N$ 种物品,每种物品都有给定的体积和价值。在 DD 看来,合理的背包安排方案是这样的:

  1. 每个人背包里装的物品的总体积恰等于包的容量。
  2. 每个包里的每种物品最多只有一件,但两个不同的包中可以存在相同的物品。
  3. 任意两个人,他们包里的物品清单不能完全相同。

在满足以上要求的前提下,所有包里的所有物品的总价值最大是多少呢?

输入格式:

第一行有三个整数:$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$大的价值是多少。
转移的时候要注意一下,要用类似于归并排序合并时的方法转移。(具体如何实现看代码)

1
2
3
4
5
6
7
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。
上代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#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;
}

最后更新: 2019年09月27日 20:22

原始链接: http://oierlin.cf/2019/08/06/【洛谷P1858】多人背包/

× 请我吃糖~
打赏二维码