fork download
copy 
  1. #include <iostream>
  2. #include <iomanip>
  3.  
  4. using namespace std;
  5.  
  6. typedef struct {
  7.         float weight;
  8.         float value;
  9.         int index;
  10. } Object;
  11.  
  12. void readData(Object *ob, int *size, float *capacity) {
  13.  
  14.      float w, v = 1;
  15.      cin>>*capacity;
  16.      while( cin ) {
  17.           cin>>w>>v;
  18.           ob[(*size)].weight = w;
  19.           ob[(*size)].value = v;
  20.           ob[(*size)].index = (*size);
  21.           (*size)+=1;
  22.      }
  23. }
  24.  
  25. int compare(const void*a, const void*b) {
  26.     Object *ob1 = (Object*)a;
  27.     Object *ob2 = (Object*)b;
  28.     return ob2->value/ob2->weight - ob1->value/ob1->weight;
  29. }
  30.  
  31. int main(int argc, char const *argv[]) {
  32.  
  33.    int size = 0;
  34.    float capacity;
  35.    Object arr[ 100 ];
  36.    readData(arr, &size, &capacity);
  37.    cout<<size-1<<" - "<<capacity<<endl;
  38.    qsort((void*)arr,size,sizeof(Object),compare);
  39.    setprecision(4);
  40.    int i = 0;
  41.    while(capacity>0) {
  42.       if(capacity>=arr[i].weight) {
  43.         capacity -= arr[i].weight;
  44.         i++;
  45.       } else {
  46.         capacity = -capacity;
  47.       }
  48.    }
  49.    for(int j = 0; j < i; ++j) {
  50.      cout<<"Object "<<arr[j].index+1<<": "<<arr[j].weight<<" "<<arr[j].value<<" - COMPLETE"<<endl;
  51.    }
  52.    if(capacity<0) {
  53.       cout<<"Object "<<arr[i].index+1<<": "<<arr[i].weight<<" "<<arr[i].value<<" - ALTERED "<<-capacity<<"kg";
  54.    }
  55.   return 0;
  56. }
Success #stdin #stdout 0.01s 5476KB
comments (?)
stdin
copy 
41
12.34 123.99
23.45 600.54
12.78 90.67
9.34 45.32
stdout
copy 
4 - 41
Object 2: 23.45 600.54 - COMPLETE
Object 1: 12.34 123.99 - COMPLETE
Object 3: 12.78 90.67 - ALTERED 5.21kg
https://ideone.com/LQ3OIF
Knapsack Continous Problem
language:
C++ (gcc 8.3)
created:
1 year ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!