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.

cellpadding="2" cellspacing="2">

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) | Incredible healing properties | 3000 | 0.3 | 0.025 |

ichor (ampules of) | Vampires blood | 1800 | 0.2 | 0.015 |

gold (bars) | Shiney shiney | 2500 | 2.0 | 0.002 |

align="left" nowrap="nowrap" valign="middle">Knapsack | align="left" nowrap="nowrap" valign="middle">For the 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 thevalue of items he is carrying away with him?**

Note:

- 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)"

src="http://lh3.ggpht.com/_ueV7OWnroeY/Sd-9LlNhkmI/AAAAAAAAAD8/4oXkLjx0xzU/Knapsack_problem_fomulae.PNG">

alt="Knapsack problem formulae" title="(Showing cell formulae)"

src="http://lh3.ggpht.com/_ueV7OWnroeY/Sd-9LlNhkmI/AAAAAAAAAD8/4oXkLjx0xzU/Knapsack_problem_fomulae.PNG">

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"

title="Solver menu"

src="http://lh6.ggpht.com/_ueV7OWnroeY/Sd-9L2VfwsI/AAAAAAAAAEU/8mlo9NrxqIg/Knapsack_problem_solver.PNG">

title="Solver menu"

src="http://lh6.ggpht.com/_ueV7OWnroeY/Sd-9L2VfwsI/AAAAAAAAAEU/8mlo9NrxqIg/Knapsack_problem_solver.PNG">

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"

src="http://lh6.ggpht.com/_ueV7OWnroeY/Sd-9L2P_QgI/AAAAAAAAAEM/Af-j8UvPRMg/Knapsack_problem_solve_optionsr.PNG">

title="Solver Options"

src="http://lh6.ggpht.com/_ueV7OWnroeY/Sd-9L2P_QgI/AAAAAAAAAEM/Af-j8UvPRMg/Knapsack_problem_solve_optionsr.PNG">

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"

src="http://lh5.ggpht.com/_ueV7OWnroeY/Sd-9Lx1yvmI/AAAAAAAAAEE/j9ZFL0JLe_k/Knapsack_problem_result.PNG">

alt="Result of Knapsack constraints problem"

title="Result of Knapsack constraints problem"

src="http://lh5.ggpht.com/_ueV7OWnroeY/Sd-9Lx1yvmI/AAAAAAAAAEE/j9ZFL0JLe_k/Knapsack_problem_result.PNG">

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.

Hi

ReplyDeleteI 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

Thanks ben.

ReplyDeleteIf 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

- Paddy.