target="_blank">knapsack problem in Python. I came
across the Solver function of OpenOffice Calc and so tried to use it to
A quick recap of the problem
A traveller gets diverted and has to make an unscheduled stop
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.
the carrying of
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?
- 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
alt="Knapsack problem formulae" title="(Showing cell formulae)"
I show the formulae in the cells in the image above.
Menu Tools-> Solver shows a form for filling in. from top to
- 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.
You also need to click the Solvers Options
button and ensure the options are set like this:
Ok the Options, then hit Solve on the Solver window and eventually you
will get the following result:
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..
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.