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 
        KnapsackLoads(p,i,g,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
        KnapsackLoads(p,i,g,value)
    end & PrintLoads(l)

// Setup all knapsack constraints...
pred KnapsackLoads(x::L[0..],y::L[0..],z::L[0..],value::L) iff 
    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) &
        PrintLoads(t)
    end

This page was created by F1toHTML