題目描述Description

小W要去軍訓了！由于軍訓基地是封閉的，小W在軍訓期間將無法離開軍訓基地。所以他沒有辦法出去買他最愛吃的零食。萬般無奈的小W只好事先買好他愛吃的零食，裝在背包里帶入軍訓基地。市場里的零食琳瑯滿目，縱然小W想把他們都帶走，然而小W的背包只有有限的容量。帶哪些零食好呢？小W給每種零食都評估了一個他的喜愛程度。另外，由于市場的零食都是散稱售賣的，所以一種零食可以只買一部分帶走。現在小W希望能挑選出最合適的購買方案，使得所購買的零食能裝進背包且喜愛程度總分最大。因為零食的種類實在是太多了，所以小W找到了聰明的你，希望你能盡快（軍訓的車隊即將出發，時間緊迫）告訴他購買方案。

輸入描述Input Description

第一行兩個整數n和w，分別表示有n種零食種類和背包總容量。接下來n行，每行兩個整數ci和vi，分別表示第i種食品占的體積和小W的喜愛程度。

輸出描述Output Description

一行一個數字，表示最優購買方案下，所能獲得的最大喜愛程度總和。保留3位小數。

樣例輸入 Sample Input

55 15 24 33 42 51

樣例輸出 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！

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstdio>
 4 #include<cstdlib>
 5 #include<cstring>
 6 #include<queue>
 7 using namespace std;
 8 typedef long long LL;
 9 inline int read()
10 {
11     int x=0,f=1;char c=getchar();
12     while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
13     while(isdigit(c)){x=x*10+c-'0';c=getchar();}
14     return x*f;
15 }
16 const int maxn=2000010;
17 struct Item
18 {
19     double w,v,s;
20     bool operator < (const Item &t)const  {return s<t.s;}
21 }a[maxn];
22 int n,ans;
23 double V;
24 double solve(int l,int r,double val)//val是當前背包容量 
25 {
26     if(l>r)return 0;
27     if(l==r)
28     {
29         if(val<a[l].v)return val*a[l].s;
30         else return a[l].w;
31     }
32     int mid=(l+r)/2;
33     double sum=0,sum2=0;
34     nth_element(a+l,a+mid,a+r+1);
35     for(int i=mid+1;i<=r;i++)sum+=a[i].w,sum2+=a[i].v;
36     //printf("%d %d %d %lf %lf %lf
",l,r,mid,sum,sum2,val);
37     if(val>sum2)return sum+solve(l,mid,val-sum2);
38     if(val==sum2)return sum;
39     if(val<sum2)return solve(mid+1,r,val);
40 }
41 int main()
42 {
43     n=read();V=(double)read();
44     int i=1;
45     while(i<=n)
46     {
47          a[i].v=(double)read();a[i].w=(double)read();
48          if(a[i].v==0)ans+=a[i].w,n--;
49          else a[i].s=a[i].w/a[i].v,i++;
50     }
51     printf("%.3f
",ans+solve(1,n,V));
52     return 0;
53 }

View Code

總結

以上是生活随笔為你收集整理的[KCOJ20170214]又一个背包的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。