问贪心算法的实现

EN

// Knapsack problem: Greedy method

// Objects: 1,  2,   3,   4,  5,  6,  7
// Profits: 10, 5,   15,  7,  6,  18, 3
// Weights: 2,  3,   5,   7,  1,  4,  1

// Fill a 15kg knapsack with the objects(they can be divisible) so that the profit is maximum

// Output should be:
// 1*first 2/3*second 1*third 0*fourth 1*fifth 1*sixth 1*seventh

#include <iostream>
#include <iomanip>
using namespace std;

char *objects[] = {"First", "Second", "Third", "Fourth", "Fifth", "Sixth", "Seventh"};
int profits[] = {10, 5, 15, 7, 6, 18, 3};
int weights[] = {2, 3, 5, 7, 1, 4, 1};
double profitPerWeight[7] = {5, 1.3, 3, 1, 6, 4.5, 3};
int bagWeight = 0;
int bagCapacity = 15;
int fraction;
int bagContent[7] = {0,0,0,0,0,0,0};
int itemToAddIndex = 0;

// function that returns the index of most profitable item in 'profitPerWeight[]'
int MaxProfitItem()
{
 int index = 0;
 int mostPr = profitPerWeight[0];
 for(int i=1; i<7; i++)
 {
  if(profitPerWeight[i] > mostPr)
  {
   mostPr = profitPerWeight[i];
   index = i;
  }
 }
 return index;
}

// function that returns true if the current fraction of an
// item can fit in the bag or false if the
// current fraction of an item cannot fit in the bag
bool itemFits(int index)
{
 if(bagWeight + weights[index] <= 15)
  return true;

 return false;
}

// function that divides an item with a specified fraction
void divideItem(int index, double fraction)
{
 weights[index] = weights[index] / fraction;
}

// function that returns which fraction of an item can fit in the bag
double getFraction(int index)
{
 double fraction;  // the fraction is initially 1
 if(itemFits(index))
 {
  fraction = 1;
 }

 else
 {
  fraction = weights[index] % bagCapacity;
 }

 return fraction;


}

// puts fraction of item in bag and updates capacity&weight of bag
void putInBag(int itemToAddIndex, double fraction)
{
 profitPerWeight[itemToAddIndex] = 0; // disegard this so it won't be seen as max next time we look for most valuable item
 bagCapacity = bagCapacity - fraction * weights[itemToAddIndex];
 bagWeight = bagWeight + fraction * weights[itemToAddIndex];
 bagContent[itemToAddIndex] = fraction;
}

// function that solves the problem using greedy approach
void knapSack()
{
  while(bagWeight<=15)
  {
   itemToAddIndex = MaxProfitItem();       // select the most profit/weight valuable item
   fraction = getFraction(itemToAddIndex); // see which fraction of it fits in the bag
   putInBag(itemToAddIndex, fraction);     // put the fraction of item which fits in bag
  }

  for(int i=0; i<7; i++)
  {
   cout << *(objects+i) << "*" << bagContent[i] << " ";
  }
}

int main()
{
 knapSack();

}