Home

More Samples

///////////////////////////////////////////////////////////////////////////////////////////////////
//
// http://rosettacode.org/wiki/Knapsack_problem/0-1#Oz
//
// A tourist wants to make a good trip at the weekend with his friends. They will go to the 
// mountains to see the wonders of nature, so he needs to pack well for the trip. He has a good 
// knapsack for carrying things, but knows that he can carry a maximum of only 4kg in it and it 
// will have to last the whole day. He creates a list of what he wants to bring for the trip but the 
// total weight of all items is too much. He then decides to add columns to his initial list 
// detailing their weights and a numerical "value" representing how important the item is for the 
// tour.
//
// Here is the list:
//
//        Item            Weight (dag)     Value
//       +--------------------------------------+
//        map                      9         150 
//        compass                 13          35 
//        water                  153         200 
//        sandwich                50         160 
//        glucose                 15          60 
//        tin                     68          45 
//        banana                  27          60 
//        apple                   39          40 
//        cheese                  23          30 
//        beer                    52          10 
//        suntan cream            11          70 
//        camera                  32          30 
//        t-shirt                 24          15
//        trousers                48          10
//        umbrella                73          40
//        waterproof trousers     42          70
//        waterproof overclothes  43          75
//        note-case               22          80
//        sunglasses               7          20
//        towel                   18          12
//        socks                    4          50
//        book                    30          10
//       +--------------------------------------+
//        Knapsack             <=400 dag       ? 
//
// The tourist can choose to take any combination of items from the list, but only one of each item
// is available. He may not cut the items, so he can only take whole units of any item.
//
// Which items does the tourist carry in his knapsack so that their total weight does not exceed 
// 4 kg, and their total value is maximised? 
//
///////////////////////////////////////////////////////////////////////////////////////////////////
//
// Query:
//
//    Knapsack()
//
// Solution:
//
//      Total weight: 396
//      Total value: 1030
//      
//      Items:
//         compass
//         sandwich
//         glucose
//         tin
//         banana
//         camera
//         waterproof trousers
//         note-case
//         sunglasses
//         towel
//         socks
//         book
//
//      Success
//      Elapsed time: 00:00:04  
//
///////////////////////////////////////////////////////////////////////////////////////////////////

local Items :< [0..]->(name:S,weight:I,value:I) =
    [
    ('map', 9, 150),
    ('compass', 13, 35),
    ('water', 153, 200),
    ('sandwich', 50, 160),
    ('glucose', 15, 60),
    ('tin', 68, 45),
    ('banana', 27, 60),
    ('apple', 39, 40),
    ('cheese', 23, 30),
    ('beer', 52, 10),
    ('suntan cream', 11, 70),
    ('camera', 32, 30),
    ('t-shirt', 24, 15),
    ('trousers', 48, 10),
    ('umbrella', 73, 40),
    ('waterproof trousers', 42, 70),
    ('waterproof overclothes', 43, 75),
    ('note-case', 22, 80),
    ('sunglasses', 7, 20),
    ('towel', 18, 12),
    ('socks', 4, 50),
    ('book', 30, 10)
    ]

proc Knapsack() iff
    // Brute force.
    // Get the maximum of all possible packing arrangements.
    max value,weight,indeces
        PackList(0,400,0,weight,0,value,Nil,indeces)
    end & Print('\nTotal weight: ',weight,'\nTotal value: ',value,'\n\nItems:') & PrintList(indeces,0)

// Go through the list of items and recursively add their weights and values.
// Each object is either packed or not: Present 0 times or 1 times.
local pred PackList(ix:<I,maxweight:<I,win:<I,wout:>I,vin:<I,vout:>I,lin:<list I,lout:>list I) iff
    if win > maxweight then 
        false   // Fail packing if over weight limit 
    end &
    if ix < Len(Items) then
        i:>[0..1] & PackList(ix+1,maxweight,win+i*Items(ix).weight,wout,vin+i*Items(ix).value,vout,(i,lin),lout)
    else
        lout = lin & wout = win & vout = vin
    end

local proc PrintList(l:<list I,ix:<I) iff
    if l = h,t then
        if h = 1 then  // 1: item is present, 0: item is missing 
            Print('\n   ',Items(ix).name) 
        end &
        PrintList(t,ix+1)
    end
        
 
     
  

This page was created by F1toHTML