fork download
  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
stdin
41
12.34 123.99
23.45 600.54
12.78 90.67
9.34 45.32
stdout
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