Chương trình C ++ để giải quyết vấn đề Fractional Knapsack

Trong bài toán Fractional knapsack, một tập hợp các mục được đưa ra, mỗi mục có trọng lượng và giá trị. Chúng ta cần chia nhỏ các mục để tối đa hóa tổng giá trị của gói và điều này có thể được thực hiện theo phương pháp tham lam.

Thuật toán

Begin
Take an array of structure Item
Declare value, weight, knapsack weight and density
Calculate density=value/weight for each item
Sorting the items array on the order of decreasing density
We add values from the top of the array to total value until the bag is full, i.e; total
value <= W
End

Mã mẫu

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef struct {
   int v;
   int w;
   float d;
} Item;
void input(Item items[],int sizeOfItems) {
   cout << "Enter total "<< sizeOfItems <<" item's values and weight" <<
   endl;
   for(int i = 0; i < sizeOfItems; i++) {
      cout << "Enter "<< i+1 << " V ";
      cin >> items[i].v;
      cout << "Enter "<< i+1 << " W ";
      cin >> items[i].w;
   }
}
void display(Item items[], int sizeOfItems) {
   int i;
   cout << "values: ";
   for(i = 0; i < sizeOfItems; i++) {
      cout << items[i].v << "\t";
   }
   cout << endl << "weight: ";
   for (i = 0; i < sizeOfItems; i++) {
      cout << items[i].w << "\t";
   }
   cout << endl;
}
bool compare(Item i1, Item i2) {
   return (i1.d > i2.d);
}
float knapsack(Item items[], int sizeOfItems, int W) {
   int i, j;
   float totalValue = 0, totalWeight = 0;
   for (i = 0; i < sizeOfItems; i++) {
      items[i].d = (float)items[i].v / items[i].w; //typecasting done (v is int and w is also int so we get final value of d as int)
   }
   sort(items, items+sizeOfItems, compare);
   /*
   uncomment if u need to check the data after sortingis done
   cout << "values : ";
   for(i = 0; i < sizeOfItems; i++) {
      cout << items[i].v << "\t";
   }
   cout << endl << "weights: ";
   for (i = 0; i < sizeOfItems; i++) {
      cout << items[i].w << "\t";
   }
   cout << endl << "ratio  : ";
   for (i = 0; i < sizeOfItems; i++) {
      cout << items[i].d << "\t";
   }
   cout << endl;
   */
   for(i=0; i<sizeOfItems; i++) {
      if(totalWeight + items[i].w<= W) {
         totalValue += items[i].v ;
         totalWeight += items[i].w;
      } else {
         int wt = W-totalWeight;
         totalValue += (wt * items[i].d);
         totalWeight += wt;
         break;
      }
   }
   cout << "Total weight in bag " << totalWeight<<endl;
   return totalValue;
}
int main() {
   int W;
   Item items[4];
   input(items, 4);
   cout << "Entered data \n";
   display(items,4);
   cout<< "Enter Knapsack weight \n";
   cin >> W;
   float mxVal = knapsack(items, 4, W);
   cout << "Max value for "<< W <<" weight is "<< mxVal;
}

Đầu ra

Enter total 4 item's values and weight
Enter 1 V Enter 1 W Enter 2 V Enter 2 W Enter 3 V Enter 3 W Enter 4 V Enter 4 W Entered data
values: 2         0         0         0
weight: 0         490642064 0         4196544
Enter Knapsack weight
Total weight in bag 0
Max value for 0 weight is 2