knapsack.cpp

#include <assert.h>

#include "knapsack.h"

#define maxcount 10

using namespace std;

// ******* DATA STRUCTURES ***********

/* struct for memoizing each M solution as well as containing the selection
 * that creates such solution */


// ******* Class Functions ****************

// Constructor given problem statement. This formalizes the problem statement
KnapSack_DP::KnapSack_DP(int capacity, vector<int> pids, catalog* cat)
{
    this->capacity  = capacity;
    this->pids      = pids;
    this->cat       = cat;

    // Sort the pids by increasing price of object
    sort(this->pids.begin(), this->pids.end(), compareByPrice);
}


KnapSack_DP::~KnapSack_DP()
{
    // TODO
}

m_elem KnapSack_DP::solve()
{

    // Initialize base step
    vector<int> sol_0;
    m_elem m_0 = {0, 0, sol_0}; // initialize base case
    Ms.push_back(m_0);


    int tprice, ttotal, tmax, tpidmax;    // temporary variables for price,
                                        // total, maximum total, and index of
                                        // the added element
    m_elem tsol;    // temporary solution

    for(int w = 1; w <= this->capacity; w++)    // increase programming table from bottom up
    {
        tmax = 0;


        for(int i = 0; i <= (int) pids.size(); i++)   // loop through all item in order
        {
            tprice = getPrice(pids[i]);
            if(tprice > w) // no need to consider any items that costs more than the weight.
            {
                break;
            }

            assert(w >= tprice); // make sure that the price not greater than the weight

            ttotal = tprice + Ms[w - tprice].opt_weight;
            if(ttotal > w) // escape if the total goes over
            {
                continue;
            }

            if (ttotal > tmax)
            {
                tmax  = ttotal;
                tpidmax = pids[i];
            }

        }
        assert (tmax <= w); // make sure that the total is less than temp capacity

        vector<int> pids_sol (Ms[w - getPrice(tpidmax)].pids_sol);
        pids_sol.push_back(tpidmax);
        tsol = {tmax, w, pids_sol};
        Ms.push_back(tsol);
    }

    return Ms.back();
}

int KnapSack_DP::getPrice(int pid)
{
    return (*cat)[pid].price;
}

bool KnapSack_DP::compareByPrice(int pid1, int pid2)
{
    return getPrice(pid1) < getPrice(pid2);
}

int KnapSack_DP::getCapacity()
{
    return this->capacity;
}



int main(int argc, char** argv) 
{
	int i;
	cout << "boobs" << endl;
	cin >> i;
	return 0;
}

knapsack.h

/*
 * knapsack.h
 *
 * Copyright 2014 Kevin Tang <ktang@caltech.edu>
 *
 * This file is available under the MIT license. See
 * http://opensource.org/licenses/MIT for more details
 *
 * This is the header file for algorithms that solve the knapsack problem
 * These functions are used to solve an optimization of funds allocated to 
 * maximize the use of DBAL at Caltech. 
 *
 */
#ifndef __knapsack_h__
#define __knapsack_h__

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
 
// ******* DATA STRUCTURES ***********

// an item
struct item
{
    int price;
    int pid;
};

// catalog
typedef std::map<int, item> catalog; // catalog

// This struct represents a memoized solution to a subproblem
struct m_elem
{
    int opt_weight;         // maximum weight up to here
    int weight;             // Weight cap of problem
    std::vector<int> pids_sol;   // vector of selected objects
};

// ******* MAIN CLASS ****************
class KnapSack_DP
{
    int capacity;           // capacity
    std::vector<int> pids;       // selection of available items
    catalog* cat;           // pointer to the catalogue
    std::vector<m_elem> Ms;      // vector for memoization

public:
    KnapSack_DP(int capacity, std::vector<int> pids, catalog* cat);
    ~KnapSack_DP();
    m_elem solve();
    
    int getPrice(int pid);
    static bool compareByPrice(const int pid1, const int pid2);

    int getCapacity();

};

// ******* HELPER FUNCTIONS **********

#endif