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