A tourist wants to make a good trip at the weekend with his friends.

They will go to the mountains to see the wonders of nature.   So he needs some items during the trip.   Food, clothing, etc.   He has a good knapsack for carrying the things, but he knows that he can carry only 4 kg weight in his knapsack, because they will make the trip from morning to evening.

He creates a list of what he wants to bring for the trip, but the total weight of all items is too much.   He adds a value to each item.   The value represents how important the thing for the tourist.

The list contains which items are the wanted things for the trip, what is the weight and value of an item, and how many units does he have from each items.



This is the list:


 Table of potential knapsack items


 item 
 weight (dag) (each) 
 value (each) 
 piece(s)


 map 
 9 
 150 
 1


 compass 
 13 
 35 
 1


 water 
 153 
 200 
 2


 sandwich 
 50 
 60 
 2


 glucose 
 15 
 60 
 2


 tin 
 68 
 45 
 3


 banana 
 27 
 60 
 3


 apple 
 39 
 40 
 3


 cheese 
 23 
 30 
 1


 beer 
 52 
 10 
 3


 suntan cream 
 11 
 70 
 1


 camera 
 32 
 30 
 1


 T-shirt 
 24 
 15 
 2


 trousers 
 48 
 10 
 2


 umbrella 
 73 
 40 
 1


 waterproof trousers 
 42 
 70 
 1


 waterproof overclothes 
 43 
 75 
 1


 note-case 
 22 
 80 
 1


 sunglasses 
 7 
 20 
 1


 towel 
 18 
 12 
 2


 socks 
 4 
 50 
 1


 book 
 30 
 10 
 2


 knapsack 
 ≤400 dag 
 ? 
 ?



The tourist can choose to take any combination of items from the list, and some number of each item is available   (see the column   piece(s)   in the list above).

He may not cut the items, so he can only take whole units of any item.



Task

Show which items does the tourist carry in his knapsack so that their total weight does not exceed 4 kg, and their total value is maximized.



Related tasks

   Knapsack problem/Unbounded
   Knapsack problem/Continuous
   Knapsack problem/0-1


#include <iostream>
#include <vector>
#include <algorithm>
#include <stdexcept>
#include <memory>
#include <sys/time.h>
 
using std::cout;
using std::endl;
 
class StopTimer
{
public:
    StopTimer(): begin_(getUsec()) {}
    unsigned long long getTime() const { return getUsec() - begin_; }
private:
    static unsigned long long getUsec()
    {//...you might want to use something else under Windows
        timeval tv;
        const int res = ::gettimeofday(&tv, 0);
        if(res)
            return 0;
        return tv.tv_usec + 1000000 * tv.tv_sec;
    }
    unsigned long long begin_;
};
 
struct KnapsackTask
{
    struct Item
    {
        std::string name;
        unsigned w, v, qty;
        Item(): w(), v(), qty() {}
        Item(const std::string& iname, unsigned iw, unsigned iv, unsigned iqty):
            name(iname), w(iw), v(iv), qty(iqty)
        {}
    };
    typedef std::vector<Item> Items;
    struct Solution
    {
        unsigned v, w;
        unsigned long long iterations, usec;
        std::vector<unsigned> n;
        Solution(): v(), w(), iterations(), usec() {}
    };
    //...
    KnapsackTask(): maxWeight_(), totalWeight_() {}
    void add(const Item& item)
    {
        const unsigned totalItemWeight = item.w * item.qty;
        if(const bool invalidItem = !totalItemWeight)
            throw std::logic_error("Invalid item: " + item.name);
        totalWeight_ += totalItemWeight;
        items_.push_back(item);
    }
    const Items& getItems() const { return items_; }
    void setMaxWeight(unsigned maxWeight) { maxWeight_ = maxWeight; }
    unsigned getMaxWeight() const { return std::min(totalWeight_, maxWeight_); }
 
private:
    unsigned maxWeight_, totalWeight_;
    Items items_;
};
 
class BoundedKnapsackRecursiveSolver
{
public:
    typedef KnapsackTask Task;
    typedef Task::Item Item;
    typedef Task::Items Items;
    typedef Task::Solution Solution;
 
    void solve(const Task& task)
    {
        Impl(task, solution_).solve();
    }
    const Solution& getSolution() const { return solution_; }
private:
    class Impl
    {
        struct Candidate
        {
            unsigned v, n;
            bool visited;
            Candidate(): v(), n(), visited(false) {}
        };
        typedef std::vector<Candidate> Cache;
    public:
        Impl(const Task& task, Solution& solution):
            items_(task.getItems()),
            maxWeight_(task.getMaxWeight()),
            maxColumnIndex_(task.getItems().size() - 1),
            solution_(solution),
            cache_(task.getMaxWeight() * task.getItems().size()),
            iterations_(0)
        {}
        void solve()
        {
            if(const bool nothingToSolve = !maxWeight_ || items_.empty())
                return;
            StopTimer timer;
            Candidate candidate;
            solve(candidate, maxWeight_, items_.size() - 1);
            convertToSolution(candidate);
            solution_.usec = timer.getTime();
        }
    private:
        void solve(Candidate& current, unsigned reminderWeight, const unsigned itemIndex)
        {
            ++iterations_;
 
            const Item& item(items_[itemIndex]);
 
            if(const bool firstColumn = !itemIndex)
            {
                const unsigned maxQty = std::min(item.qty, reminderWeight/item.w);
                current.v = item.v * maxQty;
                current.n = maxQty;
                current.visited = true;
            }
            else
            {
                const unsigned nextItemIndex = itemIndex - 1;
                {
                    Candidate& nextItem = cachedItem(reminderWeight, nextItemIndex);
                    if(!nextItem.visited)
                        solve(nextItem, reminderWeight, nextItemIndex);
                    current.visited = true;
                    current.v = nextItem.v;
                    current.n = 0;
                }
                if(reminderWeight >= item.w)
                {
                    for (unsigned numberOfItems = 1; numberOfItems <= item.qty; ++numberOfItems)
                    {
                        reminderWeight -= item.w;
                        Candidate& nextItem = cachedItem(reminderWeight, nextItemIndex);
                        if(!nextItem.visited)
                            solve(nextItem, reminderWeight, nextItemIndex);
 
                        const unsigned checkValue = nextItem.v + numberOfItems * item.v;
                        if ( checkValue > current.v)
                        {
                            current.v = checkValue;
                            current.n = numberOfItems;
                        }
                        if(!(reminderWeight >= item.w))
                            break;
                    }
                }
            }
        }
        void convertToSolution(const Candidate& candidate)
        {
            solution_.iterations = iterations_;
            solution_.v = candidate.v;
            solution_.n.resize(items_.size());
 
            const Candidate* iter = &candidate;
            unsigned weight = maxWeight_, itemIndex = items_.size() - 1;
            while(true)
            {
                const unsigned currentWeight = iter->n * items_[itemIndex].w;
                solution_.n[itemIndex] = iter->n;
                weight -= currentWeight;
                if(!itemIndex--)
                    break;
                iter = &cachedItem(weight, itemIndex);
            }
            solution_.w = maxWeight_ - weight;
        }
        Candidate& cachedItem(unsigned weight, unsigned itemIndex)
        {
            return cache_[weight * maxColumnIndex_ + itemIndex];
        }
        const Items& items_;
        const unsigned maxWeight_;
        const unsigned maxColumnIndex_;
        Solution& solution_;
        Cache cache_;
        unsigned long long iterations_;
    };
    Solution solution_;
};
 
void populateDataset(KnapsackTask& task)
{
    typedef KnapsackTask::Item Item;
    task.setMaxWeight( 400 );
    task.add(Item("map",9,150,1));
    task.add(Item("compass",13,35,1));
    task.add(Item("water",153,200,2));
    task.add(Item("sandwich",50,60,2));
    task.add(Item("glucose",15,60,2));
    task.add(Item("tin",68,45,3));
    task.add(Item("banana",27,60,3));
    task.add(Item("apple",39,40,3));
    task.add(Item("cheese",23,30,1));
    task.add(Item("beer",52,10,3));
    task.add(Item("suntancream",11,70,1));
    task.add(Item("camera",32,30,1));
    task.add(Item("T-shirt",24,15,2));
    task.add(Item("trousers",48,10,2));
    task.add(Item("umbrella",73,40,1));
    task.add(Item("w-trousers",42,70,1));
    task.add(Item("w-overclothes",43,75,1));
    task.add(Item("note-case",22,80,1));
    task.add(Item("sunglasses",7,20,1));
    task.add(Item("towel",18,12,2));
    task.add(Item("socks",4,50,1));
    task.add(Item("book",30,10,2));
}
 
int main()
{
    KnapsackTask task;
    populateDataset(task);
 
    BoundedKnapsackRecursiveSolver solver;
    solver.solve(task);
    const KnapsackTask::Solution& solution = solver.getSolution();
 
    cout << "Iterations to solve: " << solution.iterations << endl;
    cout << "Time to solve: " << solution.usec << " usec" << endl;
    cout << "Solution:" << endl;
    for (unsigned i = 0; i < solution.n.size(); ++i)
    {
        if (const bool itemIsNotInKnapsack = !solution.n[i])
            continue;
        cout << "  " << solution.n[i] << ' ' << task.getItems()[i].name << " ( item weight = " << task.getItems()[i].w << " )" << endl;
    }
 
    cout << "Weight: " << solution.w << " Value: " << solution.v << endl;
    return 0;
}