Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- using namespace std;
- struct Products{
- string name;
- int weight;
- int totalPrice;
- int unitPrice;
- int taken;
- };
- void greedyKnapsack(Products p[], int n, int capacity)
- {
- int i,currentWeight=0;
- for(i=0;i<n;i++)
- {
- if(currentWeight+p[i].weight<= capacity)
- {
- currentWeight = currentWeight+p[i].weight;
- p[i].taken = 1;
- }
- }
- cout << "--------------------------------------------\n"<<endl;
- for(i=0; i<n; i++)
- {
- cout << p[i].name << "-->" ;
- if(p[i].taken==1)
- {
- cout << "Yes\n";
- }
- else
- {
- cout << "No\n";
- }
- }
- float profit=0;
- for(i=0;i<n;i++)
- {
- if(p[i].taken == 1)
- {
- profit = profit + p[i].totalPrice;
- }
- }
- cout << "\n-------------------------------------------\n"<<endl;
- cout << "Total profit: " << profit <<endl;
- cout << "Empty Space: " << capacity-currentWeight <<endl;
- }
- int main()
- {
- int capacity;
- cout << "Input Capacity: ";
- cin >> capacity;
- int type=0;
- cout << "Input Number of Types: ";
- cin >> type;
- Products p[type];
- int i,j;
- for(i=0; i<type; i++)
- {
- cout << "Input product name: ";
- cin >> p[i].name;
- cout << "Input product weight: ";
- cin >> p[i].weight;
- cout << "Input product total price: ";
- cin >> p[i].totalPrice;
- p[i].unitPrice = p[i].totalPrice/p[i].weight;
- p[i].taken = 0;
- }
- for(i=1;i<type;++i)
- {
- for(j=0;j<(type-i);++j)
- {
- if(p[j].unitPrice<p[j+1].unitPrice)
- {
- swap(p[j],p[j+1]);
- }
- }
- }
- greedyKnapsack(p,type,capacity);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment