| 题目名称 | 53. 多人背包 |
|---|---|
| 输入输出 | bags.in/out |
| 难度等级 | ★☆ |
| 时间限制 | 2000 ms (2 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 BYVoid
于2008-07-08加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：146， 提交：299， 通过率：48.83% | ||||
 QILIN |
100 | 0.370 s | 1.12 MiB | C++ |
 NVIDIA |
100 | 0.375 s | 1.27 MiB | C++ |
 bear |
100 | 0.377 s | 1.36 MiB | C++ |
|
NVIDIA |
100 | 0.380 s | 1.27 MiB | C++ |
|
NVIDIA |
100 | 0.388 s | 1.27 MiB | C++ |
 隨風巽 |
100 | 0.401 s | 1.48 MiB | C++ |
|
NVIDIA |
100 | 0.404 s | 1.27 MiB | C++ |
|
NVIDIA |
100 | 0.407 s | 1.27 MiB | C++ |
 iortheir |
100 | 0.409 s | 1.17 MiB | C++ |
 horizon<< |
100 | 0.412 s | 1.01 MiB | C++ |
| 关于 多人背包 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
膜楼上
 confoo
2017-02-22 14:49
8楼
| ||||
|
压根没往归并排序上想，结果就各种tree维护队列，各种TLE，真是智障
| ||||
|
| ||||
|
好蠢的方法，23333
| ||||
|
| ||||
|
背包，开二维，让评测机慢慢算吧……
| ||||
|
0/1背包第K优解。我用了一个蠢方法
| ||||
|
RT
| ||||
FoolMike
521
God_is_dead
啊啦吧啦吧啦
啊吧啦吧啦吧
HouJikan
kaaala-
题目描述
- 每个人背包里装的物品的总体积恰等于包的容量。
- 每个包里的每种物品最多只有一件，但两个不同的包中可以存在相同的物品。
- 任意两个人，他们包里的物品清单不能完全相同。
DD 和好朋友们要去爬山啦！他们一共有 K 个人，每个人都会背一个包。这些包的容量是相同的，都是 V。可以装进背包里的一共有 N 种物品，每种物品都有给定的体积和价值。
在 DD 看来，合理的背包安排方案是这样的：
在满足以上要求的前提下，所有包里的所有物品的总价值最大是多少呢？
输入格式
第一行有三个整数：K、V、N。
第二行开始的 N 行，每行有两个整数，分别代表这件物品的体积和价值。
输出格式
只需输出一个整数，即在满足以上要求的前提下所有物品的总价值的最大值。
样例输入
2 10 5
3 12
7 20
2 4
5 6
1 1
样例输出
57
样例说明
一种可以得到最优解的方案是：第一个人背体积为 7、2、1 的三种物品，价值为 25。第二个人背体积为 3、7 的两种物品，价值为 32。总价值 57。
数据范围
总人数 K<=50。
每个背包的容量 V<=5000。
物品种类数 N<=200。
其它正整数都不超过 5000。
输入数据保证存在满足要求的方案。