Go deh!

Mainly Tech projects on Python and Electronic Design Automation.

Friday, April 10, 2009

Knapsack solution by OO Calc

I had previously solved the href="http://www.rosettacode.org/wiki/Knapsack_Problem"
target="_blank">knapsack problem in Python. I came
across the Solver function of OpenOffice Calc and so tried to use it to
solve knapsack.

A quick recap of the problem

A traveller gets diverted and has to make an unscheduled stop
in
what turns out to be Shangri La. Opting to leave, he is allowed to take
as much as he likes of the following items, so long as it will fit in
his knapsack, and he can carry it.
He knows that he can carry no more than 25 'weights' in total; and that
the capacity of his knapsack is 0.25 'cubic lengths'.

Looking just above the bar codes on the items he finds their
weights and volumes. He digs out his recent copy of a financial paper
and gets the value of each item.

 nowrap="nowrap" valign="middle">Item nowrap="nowrap" valign="middle">Explanation nowrap="nowrap" valign="middle">Value (each) nowrap="nowrap" valign="middle">weight nowrap="nowrap" valign="middle">Volume (each) panacea(vials of) Incrediblehealing properties 3000 0.3 0.025 ichor(ampules of) Vampiresblood 1800 0.2 0.015 gold(bars) Shineyshiney 2500 2.0 0.002 align="left" nowrap="nowrap" valign="middle">Knapsack align="left" nowrap="nowrap" valign="middle">Forthe carrying of align="left" nowrap="nowrap" valign="middle">- align="left" nowrap="nowrap" valign="middle"><=25 align="left" nowrap="nowrap" valign="middle"><=0.25

He can only take whole units of any item,, but there is much
more of any item than he could ever carry

How many of each item does he take to maximise the
value of items he is carrying away with him?

Note:

1. There are four solutions that maximise the value taken.
Only one need be given.

OO Calc setup

I am using version 3.0.1. I opened a new spreadsheat and literally
cut-n-pasted the above table into the sheet. The solver needs to be
able to change some cells (the variables) that affect one cell
containing the value to optimise.. I added the table in blue, at the
right of the  figure below to calculate the value, weight and
volume of what is in the knapsack based on the amount of each item
chosen, so you can change what is in the style="font-weight: bold;">Number column and
get new totals calculated in the Totals
row

style="width: 914px; height: 444px;"
alt="Knapsack problem formulae" title="(Showing cell formulae)"

I show the formulae in the cells in the image above.

The Solver

Menu Tools-> Solver shows a form for filling in. from top to
bottom:

• The target cell is the cell I want to maximise, which is
the total value of all items in cell H8

• I want to Maximise.

• I want to change the Number
of each item i.e. vary cells G4:G6

• My limiting conditions are:

• The weight is <= 25

• The volume is <= 0.25

• The Number of each item cannot be negative.

style="width: 455px; height: 373px;" alt="Solver Menu"

You also need to click the Solvers Options
button and ensure the options are set like this:

style="width: 431px; height: 286px;" alt="Solver Options"
title="Solver Options"

Ok the Options, then hit Solve on the Solver window and eventually you
will get the following result:

style="width: 914px; height: 444px;"
alt="Result of Knapsack constraints problem"
title="Result of Knapsack constraints problem"

The solver has correctly determined that carrying no panacea, fifteen
ampules of ichor, and eleven gold bars will maximise the value, subject
to the given constraints..

Comment

Their are actually other values that give the same total value under
the same constraints but I can't find an easy way for the solver to
give them all.

END.

1. Hi

I solved the problem with a linear solver (glpk). I used the module pulp in Python, it's really easy to generate a problem like this.

Here is the source file:
http://paste.pocoo.org/show/112053/

And the Output:
http://paste.pocoo.org/show/112054/

Ben

2. Thanks ben.
If I had other types of constraints problems then I would have to use specialist packages of course, such as your use of glpk, and their is also http://labix.org/python-constraint