[KCOJ20170214]又一个背包
2024-09-07 09:54:14
题目描述 Description
|
小W要去军训了!由于军训基地是封闭的,小W在军训期间将无法离开军训基地。所以他没有办法出去买他最爱吃的零食。万般无奈的小W只好事先买好他爱吃的零食,装在背包里带入军训基地。市场里的零食琳琅满目,纵然小W想把他们都带走,然而小W的背包只有有限的容量。带哪些零食好呢?小W给每种零食都评估了一个他的喜爱程度。另外,由于市场的零食都是散称售卖的,所以一种零食可以只买一部分带走。现在小W希望能挑选出最合适的购买方案,使得所购买的零食能装进背包且喜爱程度总分最大。因为零食的种类实在是太多了,所以小W找到了聪明的你,希望你能尽快(军训的车队即将出发,时间紧迫)告诉他购买方案。
|
输入描述 Input Description
|
第一行两个整数n和w,分别表示有n种零食种类和背包总容量。 接下来n行,每行两个整数ci和vi,分别表示第i种食品占的体积和小W的喜爱程度。 |
输出描述 Output Description
|
一行一个数字,表示最优购买方案下,所能获得的最大喜爱程度总和。保留3位小数。
|
样例输入 Sample Input
|
5 5
1 5 2 4 3 3 4 2 5 1 |
样例输出 Sample Output
|
11.000
|
数据范围及提示 Data Size & Hint
|
n <= 2000000,w <= 2*10^9,0<=ci <= 100,0<=vi<=100
|
一道部分背包问题。这道题按性价比排序然后贪心取肯定是没有问题的,但是复杂度是O(n log n)有点大,像我们学校OJ对于n=2000000的肯定是跑不下来的。所以我们要O(n)做这道题。乍一想,发现完全没有思路,应该有一点灵感就是类似于O(n)求第K大数一样,一个用的是O(n log n)排序,一个是nth_element O(n)做的。于是我们就想分治做这道题,把问题分为更小的子问题。算出每个物品的性价比之后,我们nth_element求出中位数,这样这个数列的左边就变成比中位数小的,右边就变成比中位数大的。然后我们暴力扫一遍右边的价值和,判断一下,然后就好办了。复杂度分析的话,这个东西1+1/2+1/4+1/8+...+1/2^n是小于2的,所以类似的话,复杂度就是O(n)。本题还有一个坑点,就是空间有可能是0!
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
using namespace std;
typedef long long LL;
inline int read()
{
int x=,f=;char c=getchar();
while(!isdigit(c)){if(c=='-')f=-;c=getchar();}
while(isdigit(c)){x=x*+c-'';c=getchar();}
return x*f;
}
const int maxn=;
struct Item
{
double w,v,s;
bool operator < (const Item &t)const {return s<t.s;}
}a[maxn];
int n,ans;
double V;
double solve(int l,int r,double val)//val是当前背包容量
{
if(l>r)return ;
if(l==r)
{
if(val<a[l].v)return val*a[l].s;
else return a[l].w;
}
int mid=(l+r)/;
double sum=,sum2=;
nth_element(a+l,a+mid,a+r+);
for(int i=mid+;i<=r;i++)sum+=a[i].w,sum2+=a[i].v;
//printf("%d %d %d %lf %lf %lf\n",l,r,mid,sum,sum2,val);
if(val>sum2)return sum+solve(l,mid,val-sum2);
if(val==sum2)return sum;
if(val<sum2)return solve(mid+,r,val);
}
int main()
{
n=read();V=(double)read();
int i=;
while(i<=n)
{
a[i].v=(double)read();a[i].w=(double)read();
if(a[i].v==)ans+=a[i].w,n--;
else a[i].s=a[i].w/a[i].v,i++;
}
printf("%.3f\n",ans+solve(,n,V));
return ;
}
最新文章
- 20145223《Java程序程序设计》第3周学习总结
- 安装、设置与启动MySql5.1.30绿色版的方法
- 栈上连续定义的int变量,地址相差12个字节
- POJ2586Y2K Accounting Bug
- Ubuntu的默认root密码
- 《Visual C++ 程序设计》读书笔记 ----第8章 指针和引用
- 对于 NSLayoutConstraint 不执行动画的处理:
- 一次oracle大量数据删除经历
- uva 1390 - Interconnect(期望+哈希+记忆化)
- 【Unity优化】Unity优化技巧进阶开篇
- Java中的throw和throws的区别
- JAVA学习笔记 (okHttp3的用法)
- hyperledge工具-configtxlator
- 框架tensorflow1
- 【POI每日题解 #9】SKA-Piggy Banks
- 在.net Core 使用PDF模板文件生成PDF文件,代替WEB打印控件!
- SharePoint 2013 一次性上传文件大小限制
- 20145201李子璇 《网络对抗》 Web基础
- Linux下编译busybox时出现的问题
- MySQL事务异常