Facebook
From Greedy, 4 Years ago, written in C++.
Embed
Download Paste or View Raw
Hits: 148
  1. //knapsack
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4.  
  5. struct item{
  6.     int weight,price;
  7.     double PUprice;
  8. }arr[10004];
  9.  
  10. bool cmp(item a, item b){
  11.     if(a.PUprice>=b.PUprice)return true;
  12.     else return false;
  13. }
  14.  
  15. int main(){
  16.     int KScapacity,items;
  17.     double profit=0.0;
  18.     scanf("%d %d",&KScapacity,&items);
  19.     for(int i=0;i<items;i++){
  20.         scanf("%d",&arr[i].weight);
  21.     }
  22.     for(int i=0;i<items;i++){
  23.         scanf("%d",&arr[i].price);
  24.         arr[i].PUprice=(arr[i].price*1.0)/arr[i].weight;
  25.     }
  26.     sort(arr,arr+items,cmp);
  27.     for(int i=0;i<items;i++){
  28.         if(arr[i].weight>=KScapacity){
  29.             profit=profit+arr[i].PUprice*KScapacity;
  30.             arr[i].weight=arr[i].weight-KScapacity;
  31.             KScapacity=0;
  32.             break;
  33.         }
  34.         else{
  35.             KScapacity=KScapacity-arr[i].weight;
  36.             profit=profit+arr[i].price;
  37.         }
  38.     }
  39.     printf("%.5lf\n",profit);
  40. }
  41.