KnapsackBB.cpp

// Solving Knapsack problem using Branch and Bound - Tu Hoang - [email protected]
// The sole question of this problem is: If you have a backpack of capacity C (weight) and you have a list of items which weigh differently (w1, w2, etc) and have different values (p1, p2, etc), which is the best combination of items to meet these requirements:
// 1. the total weight of items doesn't exceed C,
// 2. the total profit is the most possible maximal.
// Simply speaking, if you are a thief and you are stealing stuff from a store, which items should you choose to carry with you in order that you gain the most?

#include <iostream>
#include <iomanip>
#include <fstream>
#define CAPACITY 16
using namespace std;

// --------------------------------------------------------------------------
// STRUCTURE DECLARATION & GLOBAL VARIABLES                  //
// --------------------------------------------------------------------------
struct itemProperty {
  int profit, weight, ratio; 
};
struct nodeValues {
  int ifTerminate, itemAvailability, currentProfit, currentWeight, upperBound; 
};

nodeValues itemsProceed [17][5];
int numberOfItems = 4; 
int numberOfIteraries = 16; // Store orders of iteraries
itemProperty arrayOfItems [5]; // Store items' info (weight, profit, ratio) 
int maxProfit = 0, nodex, nodey;

// --------------------------------------------------------------------------
// PROTOTYPES                                //
// --------------------------------------------------------------------------
void readData();
void calculateProfit(int,int);
void calculateWeight(int,int);
void calculateBound(int,int);
void findMaxP();

// --------------------------------------------------------------------------
// MAIN PROGRAM                                //
// --------------------------------------------------------------------------
int main () {
  readData();
  int i, j, k;
  for (i=1; i<=numberOfIteraries; i++) 
    for (j=1; j<=numberOfItems; j++) {
        if ((itemsProceed[i][j-1].ifTerminate == 1)&&(j>1)) 
          itemsProceed[i][j].ifTerminate = 1;
        else {
          calculateWeight(i,j);
          calculateProfit(i,j);
          calculateBound(i,j);
          if ((itemsProceed[i][j].currentProfit > maxProfit)&&(itemsProceed[i][j].ifTerminate==0)) {
            maxProfit = itemsProceed[i][j].currentProfit; nodex = i; nodey = j;}
        }
    }
  findMaxP();
  return 0;
}

void readData() {
  ifstream inputProceeding ("itemsProceed.txt");
  ifstream inputInfo ("itemsInfo.txt");
  int i, j;

  for (i=1; i<=numberOfIteraries; i++)
    for (j=1; j<=numberOfItems; j++)
      inputProceeding >> itemsProceed[i][j].itemAvailability;
  for (i=1; i<=numberOfItems; i++)
    inputInfo >> arrayOfItems[i].profit >> arrayOfItems[i].weight >> arrayOfItems[i].ratio;

  // Print data on the screen
  cout << "------ ITEMS DATA ------" << endl
     << "#  Profit  Weight  Ratio" << endl;
  for (i=1; i<=numberOfItems; i++) 
    cout << i << "  " << arrayOfItems[i].profit << "      " << arrayOfItems[i].weight << "       " << arrayOfItems[i].ratio << endl;
  cout << "------------------------" << endl;
}

void calculateWeight (int i, int j) {
  int k, currentWeight = 0;
  for (k=1; k<=j; k++)
    if (itemsProceed[i][k].itemAvailability == 1) 
      currentWeight = currentWeight + arrayOfItems[k].weight;
  if (currentWeight > CAPACITY)
    itemsProceed[i][j].ifTerminate = 1;
  else { itemsProceed[i][j].currentWeight = currentWeight; itemsProceed[i][j].ifTerminate = 0; }
}

void calculateProfit (int i, int j) {
  int k, currentProfit;
  currentProfit = 0;
  for (k=1; k<=j; k++)
    if (itemsProceed[i][k].itemAvailability == 1) 
      currentProfit = currentProfit + arrayOfItems[k].profit;
  itemsProceed[i][j].currentProfit = currentProfit;
}

void calculateBound (int i, int j) {
  int k, tempWeight = 0, tempProfit = 0, tempRatio;
  for (k=1; k<=j; k++)
    if ((itemsProceed[i][k].itemAvailability==1)&&(tempWeight+arrayOfItems[k].weight<=CAPACITY)) {
      tempWeight+=arrayOfItems[k].weight;
      tempProfit+=arrayOfItems[k].profit;
    }
  while ((k<=numberOfItems)&&(tempWeight+arrayOfItems[k].weight<=CAPACITY)) {
    tempWeight+=arrayOfItems[k].weight;
    tempProfit+=arrayOfItems[k].profit;
    k=k+1;
  }

  if (k>numberOfItems) tempRatio=0; 
  else tempRatio = arrayOfItems[k].ratio;

  itemsProceed[i][j].upperBound = tempProfit + (CAPACITY - tempWeight)*tempRatio;
}

void findMaxP () {
  int j;
  cout << ">> Maximal profit: " << maxProfit << endl
     << ">> Items taken: ";
  for (j=1; j<= nodey; j++)
    if (itemsProceed[nodex][j].itemAvailability == 1) cout << j << " ";
  cout << "\n>> Total weight: " << itemsProceed[nodex][nodey].currentWeight << endl
     << ">> Upper bound: " << itemsProceed[nodex][nodey].upperBound << endl;
  
}

// --------------------------------------------------------------------------
// ADDITIONAL FUNCTIONS FOR VALIDATION                     //
// --------------------------------------------------------------------------
  // Print data on the screen
  // for (i=1; i<=numberOfIteraries; i++) {
  //  for (j=1; j<=numberOfItems; j++) 
  //    if (itemsProceed[i][j].ifTerminate == 0)
  //      cout << setw(5) << itemsProceed[i][j].itemAvailability << "[P=" << setw(2) << itemsProceed[i][j].currentProfit << "]"
  //         << "[B=" << setw(3) << itemsProceed[i][j].upperBound << "]";
  //    else cout << setw(5) << itemsProceed[i][j].itemAvailability << "[   !][   !]";
  //  cout << "\n";
  // }