Home More Samples
```
///////////////////////////////////////////////////////////////////////////////
//
// http://rosettacode.org/wiki/Knapsack_problem/Unbounded
//
// 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.
//
// Item                 Explanation        Value (each)  Weight  Volume (each)
// +---------------------------------------------------------------------------+
// panacea (vials of)   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         |
// +---------------------------------------------------------------------------+
// Knapsack             For the carrying                 <=25    <=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?
//
///////////////////////////////////////////////////////////////////////////////
//
// Query:
//
//    KnapsackUnbounded()
//
// Solution:
//
//      Value:54500
//      Panacea: 0 Ichor: 15 Gold: 11
//      Panacea: 3 Ichor: 10 Gold: 11
//      Panacea: 6 Ichor: 5 Gold: 11
//      Panacea: 9 Ichor: 0 Gold: 11
//      Success
//      Elapsed time: 00:00:00
//
///////////////////////////////////////////////////////////////////////////////

WeightPana  :< L = 3
WeightIchor :< L = 2
WeightGold  :< L = 20

VolumePana  :< L = 25
VolumeIchor :< L = 15
VolumeGold  :< L = 2

ValuePana  :< L = 3000
ValueIchor :< L = 1800
ValueGold  :< L = 2500

// Max values the knapsack can handle
WeightKnapsack :< L = 250
VolumeKnapsack :< L = 250

proc KnapsackUnbounded() iff
// First find the maximum value of all possible loads
max value
end & Print('Value:',value)  &

// Knowing the maximum value, collect all
// loads with the maximum value into a list of all solutions
all p,i,g in l

// Setup all knapsack constraints...
x*WeightPana + y*WeightIchor + z*WeightGold <= WeightKnapsack &
x*VolumePana + y*VolumeIchor + z*VolumeGold <= VolumeKnapsack &
value = x*ValuePana + y*ValueIchor + z*ValueGold

// Print out the list of all solutions one by one
local proc PrintLoads(l :< list(pana:L,ichor:L,gold:L)) iff
if l = h,t then
Print('\nPanacea: ',h.pana,' Ichor: ',h.ichor,' Gold: ',h.gold) &