#include <iostream>
#include <string>
#include <fstream>
#include <vector>
#include <math.h>
#include <queue>
#include <iomanip>
#include <cctype>
#include <time.h>
using namespace std;
#include "Nodes.h"
/*
 * The purpose of this program is to solve the 0/1 Knapsack problem.
 * This will be done utilizing the Best-First with Branch and Bound Pruning Algorithm,
 * along with Dynamic Programming.  
*/
void readFile (string, vector< int >&);
int maxValue (int, int);
int dynamicProgrammingKnapsack (int, int, int [], int []);
void sort (int, int [], int []);
double calcMaxProfits (int, int, int [], int [], node &);
int knapsackThree (int, int, int [], int []);
 node::node()//http://www.ces.clemson.edu/~petersj/Agents/BasicVoidGraphs/node71.html
 {
     l = 0;
     cw =0;
     cp =0;
     b = 0.0;
 }
 node::node(const node& newNode)
 {
     l = newNode.l;
     cw = newNode.cw;
     cp = newNode.cp;
     b = newNode.b;
 }
 node::node(int level, int weight, int profit, double bound)
 :l(level) ,cw(weight) ,cp(profit) ,b(bound)
 {}             
 node::~node(){}
 int node::operator<(const node & newNode) const//930
 {
     return (b > newNode.b);
 }
  int node::operator==(const node & newNode) const
 {
     return (b == newNode.b);
 }
 int node::operator<=(const node & newNode) const
 {
     return (b >= newNode.b);  
 }   
 int node::operator!=(const node & newNode) const
 {
     return (b != newNode.b);
 }
 int node::operator>(const node & newNode) const
 {
     return (b < newNode.b);
 }
//Calculate maximum possible profit of a node
double calcMaxProfits (int numberOfItems, int maxSize, int profit[], int weight[], node & aNode)
{
    int nextLevel;
    int totalW;
    double bound;
    if (aNode.getWeights() > maxSize)
	{
        bound = 0;
	}
    else
    {
        bound = aNode.getProfits();
        nextLevel = aNode.getLevel () + 1;
        totalW = aNode.getWeights();
        while ((nextLevel <= numberOfItems) && totalW + weight[nextLevel-1] <= maxSize)
        {
            totalW += weight[nextLevel-1];
            bound += profit[nextLevel-1];
            nextLevel++;
        }
        if (nextLevel <= numberOfItems)
        {
            bound += (double)(maxSize - totalW) * profit[nextLevel-1] / weight[nextLevel-1];
	    }
    }
    return bound;
}

/*
* Dynamic Programming Algorithm for the Knapsack Problem
*/
/*
Dynamic Programming Algorithm for 0-1 Knapsack Problem

We use the following data structures and variables:

    n -- The number of items
    W -- The capacity of the knapsack
    v [n] -- An array that contains the profit for each individual item
    w [n] -- An array that contains the weight for each individual item
    P [n][W+1] -- The two-dimensional array we'll fill out to find the final solution

Algorithm

dp01knapsack (v, n, W, P)
{
    for (k = 0; k <= W; k++)
        P [0,k] = 0;

    for (i = 1; i <= n; i++)
    {
        P [i,0] = 0;

        for (k = 1; k <= W; k++)
        {
            if (w[i] <= k)
                P [i][k] = max (P [i-1][k], v [i] + P [i-1][k - w[i]])
            else
                P [i][k] = P [i-1][k]
        }
    }
}
*/
int dynamicProgrammingKnapsack (int n, int capacity, int v[], int w[])
{
    int p[n][capacity + 1];
    int copy;
    for (int k = 0; k <= capacity; k++)
        p[0][k] = 0;
    for (int i = 0; i < n; i++)
    {
        p [i][0] = 0;
        for (int k = 1; k <= capacity; k++)
        {
            copy = w[i];
            if (copy <= k)
                p[i][k] = maxValue (p[i - 1][k], (v[i] + p[i - 1][k-copy]));
            else
                p[i][k] = p[i - 1][k];
        }
    }
    return p[n - 1][capacity];
}
//Use best-first search BRANCH & BOUND solve 0/1 Knapsack
int knapsackThree (int numberOfItems, int maxSize, int profit[], int weight[])
{
    priority_queue <node> PQ;
    int maxProfit = 0;
    double vBound;
    double uBound;
    node v;
    vBound = calcMaxProfits (numberOfItems, maxSize, profit, weight, v);
    v.setBound (vBound);
    PQ.push (v);
    while (!PQ.empty())
    {
        v = PQ.top();
        node u;
        PQ.pop ();
        if (v.getBound() > maxProfit)//
        {
            int level = v.getLevel () + 1;
            u.setLevel (level);
            u.setWeights(v.getWeights() + weight [level - 1]);
            u.setProfits(v.getProfits() + profit [level - 1]);
            if ((u.getWeights() <= maxSize) && (u.getProfits() > maxProfit))
			{
                maxProfit = u.getProfits();
			}
            uBound = calcMaxProfits (numberOfItems, maxSize, profit, weight, v);
            u.setBound (uBound);
            if (u.getBound () > maxProfit)
			{
                PQ.push (u);
			}
            u.setWeights (v.getWeights());
            u.setProfits (v.getProfits());
            u.setBound (calcMaxProfits (numberOfItems, maxSize, profit, weight, v));
            if (u.getBound () > maxProfit)
			{
                PQ.push (u);
			}
        }
    }
    return maxProfit;
}
//Input text files for multiple files
void readFile (string infile, vector<int> &data)
{
	//const char* filename = "values.txt";   // Name of the file to read
    /*ifstream inFile(filename);     
    if(!infile)
	{
        cout << endl << "Failed to open file " << filename;
		exit(0);
	}*/
    ifstream inputFile (infile.c_str());
    if (inputFile.fail())
	{
        cout << "Failed to open file " << endl;
		exit(0);
	}
    int number;
    int i = 0;
    for (; inputFile >> number; i++)
	{
        data.push_back (number);
	}
}

/*
* maximum value of 2 integers
*/

int maxValue (int first, int second)
{
    if (first < second)
	{
        return second;
	}
    else
	{
        return second;
	}
}
    /*public static int min(int first,int second)
    {
	    if(first <= second)
		{
		    return first;
		}
	    else
		{
		    return second;
		}
    }*/
int main ()
{
    int numberOfIntegers;
    int maxSize;
    int maxProfit;
    clock_t current;//clock_t = clock ticks
    clock_t end;
    vector< int > data;
    string infile;
    int choice;
	//for(;;)
	//{
	cout << "********" << "\nPlease choose the amount of Weight and Items in the Knapsack,\nto solve the 0/1 Knapsack Problem: " << endl;
    cout << " 1.  8 Inputs of Weight and Items" << endl;
    cout << " 2.  9 Inputs of Weight and Items" << endl;
    cout << " 3.  10 Inputs of Weight and Items" << endl;
    cout << " 4.  11 Inputs of Weight and Items" << endl;
    cout << " 5.  12 Inputs of Weight and Items" << endl;
    cout << " 6.  Special Test with 2 Inputs of Weight and Items" << endl;
    cout << " 7.  Special Test with 4 Inputs of Weight and Items" << endl;
    cout << " 8.  Special Test with 6 Inputs of Weight and Items" << endl;
    cout << " 9.  Special Test with 20 Inputs of Weight and Items" << endl;
    cout << " 10.  Special Test with 50 Inputs of Weight and Items" << endl;
    cout << " 11.  Special Test with 100 Inputs of Weight and Items" << endl;
    cout << " 12.  Special Test with 5 Inputs of Weight and Items, the assignment example." << endl;
    cout << " 13.  To Quit Program." << endl;
    cout << "Enter a Number: ";
    cin >> choice;
    switch (choice)
    {
        case 1:
          infile = "size8.txt";
          break;
        case 2:
          infile = "size9.txt";
          break;
        case 3:
          infile = "size10.txt";
          break;
        case 4:
          infile = "size11.txt";
          break;
        case 5:
          infile = "size12.txt";
          break;
        case 6:
          infile = "size2.txt";
          break;
        case 7:
          infile = "size4.txt";
          break;
        case 8:
          infile = "size6.txt";
          break;
        case 9:
          infile = "size20.txt";
          break;
        case 10:
          infile = "size50.txt";
          break;
        case 11:
          infile = "size100.txt";
          break;
        case 12:
          infile = "size5.txt";
          break;
        case 13:
		  cout << "Ending Program." << endl;
          exit(0);
          break;
        default:
          cout << "Please enter only numbers between 1 and 12." << endl;
          break;
    }
    readFile (infile, data);
    maxSize = data[0];
    numberOfIntegers = data[1];
    int profit[numberOfIntegers];
    int weight[numberOfIntegers];
    for (int i = 2, k = 0; i < data.size (); i += 2, k++)
    {
        profit[k] = data [i];
        weight[k] = data [i+1];
    }
    current = clock();//implicit
    maxProfit = dynamicProgrammingKnapsack (numberOfIntegers, maxSize, profit, weight);
    end = clock();
    cout << "\nDynamic Programming Maximum Profit = " << maxProfit << endl;
    cout << "Dynamic Programming Time = " << end - current << endl;
    current = clock();
    maxProfit = knapsackThree (numberOfIntegers, maxSize, profit, weight);
    end = clock();
    cout << "Branch and Bound Maximum Profit = " << maxProfit << endl;
    cout << "Branch and Bound Algorithm's Time = " << end - current << endl;
	cout << "********" << endl;
}