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.

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 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)"
src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjSTTwTk_nEMgY1qLVv_QXSamy1aaWjm-H73uDgKHNjbvVB0QeTQR-EVT5tCoZtaWPjmLw3RwEbFD5kBXUJ31NSYXgM-JeYFub6uyU1ZIjFKXj1e6ltYRnG3beA0o7jgjED6D3i/">

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="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg_hFwnFTntRnmBiKs5Be81nQN6-LVoVgsi94Yl6FTgi1eM3a2IijSDPcmUOdjbh2ME_jNSpWqkScBW-9KHrl952p7MXhYT8lV_csPjRzeciF1i3Qij3K3m5JAgXQQF4by_bGoH/">

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="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjYg4BmKl0Ye99EgQ7bGvj4D_xEkf-oUNIug2hvpp9PAmjsa048nuFPSSdtMsYysNvh98NAMMpphy7jWQHRZhXWHg8fgvcUY_iH2WnsDAc5cUITezPm93HXGvNmQpx1Fj99Gxk-/">

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="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgoq_CC0HfR9EzsFU6E9dXcxmLk1zXhqZxkuu2tCe1DWK-_REuVKnTHBGO9KhzvQ-cIJfskAb24DzRT8bMv2Wb5lshQw7ec5YGT6IN4VEgvR8MlCZNBM0wRJDOAgXqzn-tSZu2J/">

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.