Knapsack Implementation

Knapsack

Knapsack Implementation

by Roger gee
24 January 2015

A.05

19
ljgwacgctv,9,3
vngeryhmge,16,4
omsrhwkiv,24,2
jtxxuznisl,20,10
iduamlfxa,10,24

A.10

79
cbgswh,37,43
emrexzbg,42,14
dvmxpgs,25,46
atdtjt,39,22
bzdmwn,46,28
rlkwyj,11,32
zhwssclz,43,45
yxubgnn,30,45
xmrmabxlpn,47,22
yvfhbgmr,26,5

A.20

100
vvnqxns,31,16
qwdtvrfaqf,89,56
xegadyl,40,59
yxmrhs,34,62
qfairfqcs,81,36
pmouuoei,12,67
xkyjloeiio,25,100
yumasse,22,72
gwsgvycnq,41,10
livcmimq,62,53
ifbdlqvlsu,54,83
nomzziqtt,65,40
dfsnoei,59,29
zdozt,48,88
dvswxodwjf,23,23
prskpmbgxb,29,50
vxxjzrrywj,15,61
jllepsumy,70,68
puuhz,36,93
iudkfvkkju,94,55

B.05

40
obslvqwc,15,18
qinhmm,17,18
bmomm,7,6
sfyaititdh,25,13
ymcdfzamxk,21,15

B.10

56
nkhyiqdmhp,33,37
ilcgtl,49,32
pnpyuzo,14,25
veqtpc,45,50
ntnopd,42,48
paordyddu,33,18
mzaugo,25,46
fqoxw,23,25
loxzpyfzs,44,50
zbbtv,8,49

B.20

188
sodlptki,61,28
tjbqr,95,47
ujkfdmmo,44,35
kvrxohqpf,66,63
stiowuan,50,72
fphwikclc,79,12
eesozin,40,34
mwovgxpyr,65,26
dejvlehuw,95,78
iglat,73,38
xkixj,59,77
rkltqu,55,81
akpmbd,65,46
lkadkdlg,88,61
fqraxmlnf,37,83
celqyz,75,62
cceutdufkl,34,61
ziajcr,89,92
vbjao,44,88
bdplvezxob,98,20

ksack.cpp

#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <iterator>
#include <algorithm>
#include <stdexcept>
#include "ksack.h"
using namespace std;

// this function will read from input and solve the knapsack problem
void do_knapsack_instance(istream& input)
{
    int costLimit;
    vector<item> items;

    // read from input source; input operation will throw an 'int' when eof is reached
    if (!(input >> costLimit))
        throw runtime_error("failed to read cost-limit from input");
    try {
        while (true) {
            item itm;
            input >> itm;
            items.push_back(itm);
        }
    }
    catch (int) {}

    // create container to store knapsacks; create a knapsack
    // and build on it to generate all subsets of the items
    vector<knapsack*> sacks;
    knapsack::generate()->build(items.begin(),items.end(),sacks);

    // search through solutions for the best knapsack
    const knapsack* best = sacks[0];
    for (size_t i = 1;i < sacks.size();++i) {
        knapsack* sack = sacks[i];
        if (sack->get_cost() <= costLimit && sack->get_value() > best->get_value())
            best = sack;
    }

    // print results
    cout << *best << endl;

    // destroy knapsacks
    for (size_t i = 0;i < sacks.size();++i)
        delete sacks[i];
}

int main(int argc,const char* argv[])
{
    if (argc > 1) {
        // use gave command-line arguments; assume they are file
        // names; read from these files
        for (int i = 1;i < argc;++i) {
            ifstream file(argv[i]);
            if ( !file.is_open() ) {
                cerr << "Couldn't open file '" << argv[i] << "'\n";
                continue;
            }
            do_knapsack_instance(file);
        }
    }
    else
        // use standard input
        do_knapsack_instance(cin);
}

istream& operator >>(istream& stream,item& itm)
{
    string line;
    stringstream ss;
    do {
        getline(stream,line);
        if (line.length() > 0) {
            // simplify the input line:
            // remove commas and normalize whitespace
            for (size_t i = 0;i < line.length();++i)
                if (line[i]==',' || isspace(line[i]))
                    line[i] = ' ';
            // remove trailing whitespace (handles different kinds of newlines)
            int index = (int)line.length()-1;
            while (index>=0 && isspace(line[index]))
                --index;
            line.erase(index+1);
        }
    } while (stream && line.length()==0);
    if (stream.eof())
        // end of input
        throw int();
    if (line.length() == 0)
        throw runtime_error("unexpected empty line in input");
    ss.str(line);
    return ss >> itm.name >> itm.cost >> itm.value;
}

bool compare_item_ptr(const item* left,const item* right)
{
    return left->name < right->name;
}

// class knapsack implementation
knapsack::knapsack()
    : myCost(0), myValue(0)
{
}
/*static*/ knapsack* knapsack::generate()
{
    return new knapsack;
}
void knapsack::add(const item& item)
{
    myCost += item.cost;
    myValue += item.value;
    items.push_back(&item);
}
void knapsack::build(item::iterator iter,item::iterator end,std::vector<knapsack*>& sacks)
{
    // check to see if we have searched through all the items; if
    // so, add this sack to the sacks collection
    if (iter == end) {
        sacks.push_back(this);
        return;
    }

    // make a copy of this knapsack and add the current item to it
    knapsack* sack = new knapsack(*this);
    sack->add(*iter);
    advance(iter,1);

    // do recursive call for "left-side of tree"; this is the branch
    // that excludes the current item; call on 'this' since this object
    // did not add the current item
    this->build(iter,end,sacks);

    // do recursive call for "right-side of tree"; this is the branch
    // that includes the current item; call of the newly created copy
    // of this object
    sack->build(iter,end,sacks);
}

ostream& operator <<(ostream& stream,const knapsack& sack)
{
    stream << "Cost: " << sack.myCost << "\nValue: " << sack.myValue
           << "\nItems: ";
    if (sack.items.size() > 0) {
        vector<const item*>::const_iterator i;
        // sort the items
        sort(sack.items.begin(),sack.items.end(),compare_item_ptr);
        i = sack.items.begin();
        stream << (*i)->name;
        for (++i;i != sack.items.end();++i)
            stream << ", " << (*i)->name;
    }
    return stream;
}

ksack.h

// ksack.h
#ifndef KSACK_H
#define KSACK_H

// define item type
struct item
{
    std::string name;
    int cost, value;
    typedef std::vector<item>::const_iterator iterator;
};

// define knapsack type
class knapsack
{
    friend std::ostream& operator <<(std::ostream&,const knapsack&);
public:
    // use generator pattern
    static knapsack* generate();

    // add item to knapsack
    void add(const item&);

    // recursively build solutions; add them to sacks
    void build(item::iterator iter,item::iterator end,std::vector<knapsack*>& sacks);

    int get_cost() const // get total cost of knapsack
    { return myCost; }
    int get_value() const
    { return myValue; }
private:
    knapsack();

    int myCost; // store cost (update when item is added to sack)
    int myValue; // store value (update when item is added to sack)
    mutable std::vector<const item*> items; // items in knapsack
};

std::istream& operator >>(std::istream&,item&); // use this operator to read in an item from input
bool compare_item_ptr(const item*,const item*); // this is used by the std::sort algorithm to compare item objects using pointers
std::ostream& operator <<(std::ostream& stream,const knapsack& sack); // useful output operator for outputting knapsack

#endif