[XJOI]noip43 T2多人背包
2024-08-31 06:33:11
多人背包
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。
输入数据保证存在满足要求的方案。
解题思路:
读完题目,大概学过的人都知道是背包,只是具体怎么做的问题
***如果没学过背包问题的人,一定要去学学,这个是dp的基础,建议学习《背包九讲》
如果是单纯的01背包,f[j]=f[j-a[i]]+v[i]
那么这样只能计算最优解,如果要计算k优解呢?
我们可以增加一维,来记录当前状态下,即装了j的空间的时候的k优解
那么我们的转移就有点问题了,如何将f[j-a[i]]这样一个vector转化到f[j]这个vector
这里我们要提到归并排序,把两个有序数组合并的方法
***如果不会把两个有序数组合并的,也建议先去学习一下,这也是联赛的基础
那么这里便是把f[j]和f[j-a[i]]两个有序vector合并了
%:pragma GCC optimize()
#include<bits/stdc++.h>
using namespace std;
const int N=,K=;
int k,v,n,ans;
int a[N],va[N],res[K],f[N][K];
int main(){
scanf("%d%d%d",&k,&v,&n);
for (int i=;i<=n;++i)
scanf("%d%d",&a[i],&va[i]);
for (int i=;i<=v;++i)
for (int j=;j<=k+;++j)
f[i][j]=-;
f[][]=;
for (int i=;i<=n;++i)
for (int j=v;j>=a[i];--j)
if (f[j-a[i]][]!=-){
int l1=,l2=,tot=;
while (l1<=k&&l2<=k){
if (f[j][l1]==-||f[j-a[i]][l2]==-) break;
if (f[j][l1]>=f[j-a[i]][l2]+va[i])
res[++tot]=f[j][l1],l1++;
else res[++tot]=f[j-a[i]][l2]+va[i],l2++;
}
if (f[j][l1]==-)
while (l2<=k&&f[j-a[i]][l2]!=-) res[++tot]=f[j-a[i]][l2]+va[i],l2++;
else if (f[j-a[i]][l2]==-)
while (l1<=k&&f[j][l1]!=-) res[++tot]=f[j][l1],l1++;
for (int l=;l<=min(tot,k);++l) f[j][l]=res[l];
}
for (int i=;i<=k;++i)
ans+=f[v][i];
printf("%d",ans);
}
总结:这道也算是背包问题的一点拓展,当然还有更多的问题等着读者去解决
最新文章
- bzoj3052: [wc2013]糖果公园
- 2014 UESTC暑前集训图论专题解题报告
- SqlServer分区表概述(转载)
- CentOS RPM安装MySQL-5.6
- Java中Split函数的用法技巧
- java获取数据库的所有列名和对应的数据库类型
- IOS 中frame与bounds的区别
- Java switch-case
- uva 10032 Problem F: Tug of War
- java HTTP请求 DefaultHttpClient is deprecated
- HTML基础的基础
- dedecms学习笔记
- BZOJ 4516: [Sdoi2016]生成魔咒 [后缀自动机]
- 论Android代码加固的意义和hook
- Java岗 面试考点精讲(基础篇02期)
- 表单取消历史保存之autocomplete的用法
- Mybatis之插件拦截
- 【转】Android动态破解微信本地数据库(EnMicroMsg.db)
- 【转】ios tableView那些事(一)创建一个简单的tableView
- struts2(三) 输入校验和拦截器
热门文章
- spring3+quartz2
- 43.mapping的理解
- App后台开发运维和架构实践学习总结(1)——App后台核心技术之用户验证方案
- Redis参数
- [bzoj1180][CROATIAN2009]OTOCI_LCT
- dubbo协议参考手册(转)
- hdu 1239
- 生产上数据库大量的latch free 导致的CPU资源耗尽的问题的解决
- C++ exit 与 return 浅析
- [ACM] hdu 1035 Robot Motion (模拟或DFS)