Skip to content

Instantly share code, notes, and snippets.

@TangerineCat
Created July 13, 2014 05:25
Show Gist options
  • Save TangerineCat/48c46722881756c36156 to your computer and use it in GitHub Desktop.
Save TangerineCat/48c46722881756c36156 to your computer and use it in GitHub Desktop.
#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
*
* 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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment