// This program demonstrates solves the knapsack problem

// By: Chris Gregg
// Date: April 23, 2018

#include <iostream>
#include "console.h"
#include "vector.h"
#include "simpio.h"

using namespace std;

// objectT struct
struct objectT {
    int weight;
    int value;
};

// function prototypes
int fillKnapsack(Vector<objectT> &objects, int targetWeight);
int fillKnapsack(Vector<objectT> &objects, int weight, int score);

int main() {
    // solution: 44
    int values[] = {12,10,8,11,14,7,9};
    int weights[] = {4,6,5,7,3,1,6};
    int targetWeight = 18;

    // solution: 67
    //int values[] = {5,20,3,50,5,4,15,12,6,7};
    //int weights[] = {6,15,11,12,6,11,13,7,17,13};
    //int targetWeight = 25;

    // solution: 7
    //int values[] = {3,4,5,6};
    //int weights[] = {2,3,4,5};
    //int targetWeight = 5;

    int numItems = sizeof(values) / sizeof(int);

    Vector<objectT> testObjects;

    for (int i=0; i < numItems; i++) {
        objectT object;
        object.value = values[i];
        object.weight = weights[i];
        testObjects.add(object);
    }

    cout << "Best solution has a best score of: "
         << fillKnapsack(testObjects, targetWeight) << endl;
    return 0;
}

int fillKnapsack(Vector<objectT> &objects, int targetWeight) {
    return fillKnapsack(objects,targetWeight,0);
}

// solution 1
int fillKnapsack(Vector<objectT> &objects, int weight, int bestScore) {
    if (weight < 0) return 0; // we tried too much weight!
    int localBestScore = bestScore;
    int obSize = objects.size();
    for (int i = 0; i < obSize; i++) {
        objectT originalObject = objects[i];
        int currValue = bestScore + originalObject.value;
        int currWeight = weight - originalObject.weight;
        // remove object for recursion
        objects.remove(i);
        currValue = fillKnapsack(objects,currWeight,currValue);
        if (localBestScore < currValue) {
            localBestScore = currValue;
        }
        // replace
        objects.insert(i,originalObject);
    }
    return localBestScore;
}

// solution 2
/*int fillKnapsack(Vector<objectT> &objects, int weight, int bestScore) {
    if (weight < 0 or objects.isEmpty()) return 0; // we tried too much weight!
    int localBestScore = bestScore;

    objectT originalObject = objects[0];
    objects.remove(0);

    int currValue = bestScore + originalObject.value;
    int currWeight = weight - originalObject.weight;

    int maximum;
    int without = maximum = fillKnapsack(objects,weight,bestScore);
    if (weight >= 0) {
        // try by using the object
        int with = fillKnapsack(objects,currWeight,currValue);
        maximum = max(with,without);
    }

    localBestScore = max(localBestScore,maximum);
    // replace
    objects.insert(0,originalObject);
    return localBestScore;
}*/

