Knapsack problem/Bounded
You are encouraged to solve this task according to the task description, using any language you may know.
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 some items during the trip. Food, clothing, etc. He has a good knapsack for carrying the things, but he knows that he can carry only 4 kg weight in his knapsack, because they will make the trip from morning to evening. He creates a list of what he wants to bring for the trip, but the total weight of all items is too much. He adds a value to each item. The value represents how important the thing for the tourist. The list contains which items are the wanted things for the trip, what is the weight and value of an item, and how many units does he have from each items.
This is the list:
| item | weight (dag) (each) | value (each) | piece(s) |
|---|---|---|---|
| map | 9 | 150 | 1 |
| compass | 13 | 35 | 1 |
| water | 153 | 200 | 2 |
| sandwich | 50 | 60 | 2 |
| glucose | 15 | 60 | 2 |
| tin | 68 | 45 | 3 |
| banana | 27 | 60 | 3 |
| apple | 39 | 40 | 3 |
| cheese | 23 | 30 | 1 |
| beer | 52 | 10 | 3 |
| suntan cream | 11 | 70 | 1 |
| camera | 32 | 30 | 1 |
| T-shirt | 24 | 15 | 2 |
| trousers | 48 | 10 | 2 |
| umbrella | 73 | 40 | 1 |
| waterproof trousers | 42 | 70 | 1 |
| waterproof overclothes | 43 | 75 | 1 |
| note-case | 22 | 80 | 1 |
| sunglasses | 7 | 20 | 1 |
| towel | 18 | 12 | 2 |
| socks | 4 | 50 | 1 |
| book | 30 | 10 | 2 |
| knapsack | ≤400 dag | ? | ? |
The tourist can choose to take any combination of items from the list, and some number of each item is available (see the column "Piece(s)" of the list!). 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?
See also: Knapsack problem/Unbounded, Knapsack problem/0-1
AutoHotkey
iterative dynamic programming solution <lang AutoHotkey>Item = map,compass,water,sandwich,glucose,tin,banana,apple,cheese,beer,suntan cream
,camera,tshirt,trousers,umbrella,waterproof trousers,waterproof overclothes,notecase
,sunglasses,towel,socks,book
Weight= 9,13,153,50,15,68,27,39,23,52,11,32,24,48,73,42,43,22,7,18,4,30 Value = 150,35,200,60,60,45,60,40,30,10,70,30,15,10,40,70,75,80,20,12,50,10 Bound = 1,1,2,2,2,3,3,3,1,3,1,1,2,2,1,1,1,1,1,2,1,2
StringSplit I, Item, `, ; Put input in arrays StringSplit W, Weight,`, StringSplit V, Value, `, StringSplit B, Bound, `,
W := 400, N := I0, I0 := V0 := W0 := 0 ; W = total weight allowed, maximize total value Loop %W%
m0_%A_Index% := 0
Loop %N% { ; build achievable value matrix m [ N rows, W columns ]
j := -1+i := A_Index, m%j%_0 := 0 ; m[i,P] = max value with items 1..i, weight <=P
Loop %W% { ; m[i,P] = max_k {m[i-1,P-k*Wi]}
p := A_Index, k := 0, y := m%j%_%p%
While ++k <= B%i% && (r := p - k*W%i%) >= 0
y := y < (c:=m%j%_%r%+k*V%i%) ? c : y
m%i%_%p% := y
}
}
i := 1+j := N, p := W, s := 0 While --i, --j { ; read out solution from value matrix m
If (m%i%_%p% = m%j%_%p%)
Continue
r := p, m := m%i%_%p%, k := 1
While 0 <= (r-=W%i%) && m%j%_%r% != (m-=V%i%)
k++ ; find multiplier
t := k " " I%i% "`n" t, s += k*W%i%, p -= k*W%i%
}
MsgBox % "Value = " m%N%_%W% "`nWeight = " s "`n`n" t</lang>
Bracmat
<lang bracmat>(knapsack=
( things
= (map.9.150.1)
(compass.13.35.1)
(water.153.200.2)
(sandwich.50.60.2)
(glucose.15.60.2)
(tin.68.45.3)
(banana.27.60.3)
(apple.39.40.3)
(cheese.23.30.1)
(beer.52.10.3)
(suntan cream.11.70.1)
(camera.32.30.1)
(T-shirt.24.15.2)
(trousers.48.10.2)
(umbrella.73.40.1)
(waterproof trousers.42.70.1)
(waterproof overclothes.43.75.1)
(note-case.22.80.1)
(sunglasses.7.20.1)
(towel.18.12.2)
(socks.4.50.1)
(book.30.10.2)
)
& 0:?maxvalue & :?sack & ( add
= cumwght
cumvalue
cumsack
name
wght
val
pcs
tings
n
ncumwght
ncumvalue
. !arg
: ( ?cumwght
. ?cumvalue
. ?cumsack
. (?name.?wght.?val.?pcs) ?tings
)
& -1:?n
& whl
' ( 1+!n:~>!pcs:?n
& !cumwght+!n*!wght:~>400:?ncumwght
& !cumvalue+!n*!val:?ncumvalue
& ( !tings:
& ( !ncumvalue:>!maxvalue:?maxvalue
& !cumsack
( !n:0&
| (!n.!name)
)
: ?sack
|
)
| add
$ ( !ncumwght
. !ncumvalue
. !cumsack
(!n:0&|(!n.!name))
. !tings
)
)
)
)
& add$(0.0..!things) & out$(!maxvalue.!sack) );
!knapsack;</lang>
- Output:
1010
. (1.map)
(1.compass)
(1.water)
(2.glucose)
(3.banana)
(1.cheese)
(1.suntan cream)
(1.waterproof overclothes)
(1.note-case)
(1.sunglasses)
(1.socks)
C
C solution with caching. Code almost identical to Go and Python, only with added burden of managing memory (not much). <lang C>#include <stdio.h>
- include <stdlib.h>
- include <stdint.h>
- include <string.h>
- define max_weight 400
typedef struct { char *name; int w, v, qty; } item_t;
item_t items[] = { {"map", 9, 150, 1}, {"compass", 13, 35, 1}, {"water", 153, 200, 2}, {"sandwich", 50, 60, 2}, {"glucose", 15, 60, 2}, {"tin", 68, 45, 3}, {"banana", 27, 60, 3}, {"apple", 39, 40, 3}, {"cheese", 23, 30, 1}, {"beer", 52, 10, 3}, {"suntancream", 11, 70, 1}, {"camera", 32, 30, 1}, {"T-shirt", 24, 15, 2}, {"trousers", 48, 10, 2}, {"umbrella", 73, 40, 1}, {"w-trousers", 42, 70, 1}, {"w-overclothes", 43, 75, 1}, {"note-case", 22, 80, 1}, {"sunglasses", 7, 20, 1}, {"towel", 18, 12, 2}, {"socks", 4, 50, 1}, {"book", 30, 10, 2}, };
/* for C, the main problem is not the algorithm: it's cache management */
- define n_types (sizeof(items)/sizeof(item_t))
typedef struct { int v, w; /* value & weight total */ unsigned short n[n_types]; /* num of each item taken */ } solution_t, *solution;
solution_t *cache, *blank;
int init_cache() { /* a flat array. If problem size is large, might be a bad idea; * then again, other caching method face similar issue, too */ size_t i; size_t n_rec = (max_weight + 1) * n_types; cache = calloc(sizeof(solution_t), (n_rec + 1)); if (!cache) return 0;
for (i = 0; i <= n_rec; i++) { cache[i].v = -1; /* value = -1 means cache not used yet */ cache[i].w = 0; } (blank = cache + n_rec)->v = 0; return 1; }
solution solve(int weight, int pos) { int i, w, v, qty; solution sol, best = 0, ret;
if (pos < 0) return blank;
ret = &cache[weight * n_types + pos]; if (ret->v >= 0) return ret;
w = items[pos].w; v = items[pos].v; qty = items[pos].qty;
for (i = 0; i <= qty && weight > 0; i++, weight -= w) { sol = solve(weight, pos - 1); if (sol->v + i * v <= ret->v) continue;
best = sol; ret->v = best->v + v * i; ret->n[pos] = i; }
/* only happens if there are no solution at all, i.e. * max_weight too small to hold even one item */ if (ret->v <= 0) return blank;
ret->w = best->w + w * ret->n[pos]; memcpy(ret->n, best->n, sizeof(unsigned short) * pos);
return ret; }
int main() { int i; solution x;
init_cache(); x = solve(max_weight, n_types - 1);
printf("Taking:\n"); for (i = 0; i < n_types; i++) { if (! x->n[i]) continue; printf(" %hu %s\n", x->n[i], items[i].name); }
printf("Weight: %d Value: %d\n", x->w, x->v);
/* free(cache); */ return 0; }</lang>
Common Lisp
<lang lisp>;;; memoize (defmacro mm-set (p v) `(if ,p ,p (setf ,p ,v)))
(defun knapsack (max-weight items)
(let ((cache (make-array (list (1+ max-weight) (1+ (length items)))
:initial-element nil)))
(labels ((knapsack1 (spc items)
(if (not items) (return-from knapsack1 (list 0 0 '()))) (mm-set (aref cache spc (length items)) (let* ((i (first items)) (w (second i)) (v (third i)) (x (knapsack1 spc (cdr items)))) (loop for cnt from 1 to (fourth i) do (let ((w (* cnt w)) (v (* cnt v))) (if (>= spc w) (let ((y (knapsack1 (- spc w) (cdr items)))) (if (> (+ (first y) v) (first x)) (setf x (list (+ (first y) v) (+ (second y) w) (cons (list (first i) cnt) (third y))))))))) x))))
(knapsack1 max-weight items))))
(knapsack 400
'((map 9 150 1) (compass 13 35 1) (water 153 200 2) (sandwich 50 60 2)
(glucose 15 60 2) (tin 68 45 3) (banana 27 60 3) (apple 39 40 3)
(cheese 23 30 1) (beer 52 10 3) (cream 11 70 1) (camera 32 30 1) (T-shirt 24 15 2) (trousers 48 10 2) (umbrella 73 40 1) (trousers 42 70 1) (overclothes 43 75 1) (notecase 22 80 1) (glasses 7 20 1) (towel 18 12 2) (socks 4 50 1) (book 30 10 2))))</lang>
D
Solution with memoization. <lang d>import std.stdio, std.typecons, std.functional;
immutable struct Item {
string name; int weight, value, quantity;
}
immutable Item[] items = [
{"map", 9, 150, 1}, {"compass", 13, 35, 1},
{"water", 153, 200, 3}, {"sandwich", 50, 60, 2},
{"glucose", 15, 60, 2}, {"tin", 68, 45, 3},
{"banana", 27, 60, 3}, {"apple", 39, 40, 3},
{"cheese", 23, 30, 1}, {"beer", 52, 10, 3},
{"suntan cream", 11, 70, 1}, {"camera", 32, 30, 1},
{"t-shirt", 24, 15, 2}, {"trousers", 48, 10, 2},
{"umbrella", 73, 40, 1}, {"w-trousers", 42, 70, 1},
{"w-overcoat", 43, 75, 1}, {"note-case", 22, 80, 1},
{"sunglasses", 7, 20, 1}, {"towel", 18, 12, 2},
{"socks", 4, 50, 1}, {"book", 30, 10, 2}];
Tuple!(int,const(int)[]) chooseItem(in int iWeight, in int idx) nothrow {
alias memoize!chooseItem memoChooseItem;
if (idx < 0)
return typeof(return).init;
int bestV;
const(int)[] bestList;
with (items[idx])
foreach (i; 0 .. quantity + 1) {
immutable wlim = iWeight - i * weight;
if (wlim < 0)
break;
//const (val, taken) = memoChooseItem(wlim, idx - 1);
const val_taken = memoChooseItem(wlim, idx - 1);
if (val_taken[0] + i * value > bestV) {
bestV = val_taken[0] + i * value;
bestList = val_taken[1] ~ i;
}
}
return tuple(bestV, bestList);
}
void main() {
// const (v, lst) = chooseItem(400, items.length - 1); const v_lst = chooseItem(400, items.length - 1);
int w;
foreach (i, cnt; v_lst[1])
if (cnt > 0) {
writeln(cnt, " ", items[i].name);
w += items[i].weight * cnt;
}
writeln("Total weight: ", w, " Value: ", v_lst[0]);
}</lang>
- Output:
1 map 1 compass 1 water 2 glucose 3 banana 1 cheese 1 suntan cream 1 w-overcoat 1 note-case 1 sunglasses 1 socks Total weight: 396 Value: 1010
Go
Solution with caching. <lang go>package main import "fmt"
type Item struct { name string weight, value, qty int }
type Solution struct { v, w int qty []int }
var items = []Item { {"map", 9, 150, 1}, {"compass", 13, 35, 1}, {"water", 153, 200, 2}, {"sandwich", 50, 60, 2}, {"glucose", 15, 60, 2}, {"tin", 68, 45, 3}, {"banana", 27, 60, 3}, {"apple", 39, 40, 3}, {"cheese", 23, 30, 1}, {"beer", 52, 10, 3}, {"suntancream", 11, 70, 1}, {"camera", 32, 30, 1}, {"T-shirt", 24, 15, 2}, {"trousers", 48, 10, 2}, {"umbrella", 73, 40, 1}, {"w-trousers", 42, 70, 1}, {"w-overclothes", 43, 75, 1}, {"note-case", 22, 80, 1}, {"sunglasses", 7, 20, 1}, {"towel", 18, 12, 2}, {"socks", 4, 50, 1}, {"book", 30, 10, 2}, }
func choose(weight, pos int, cache map[string]*Solution) (int, int, []int) { if pos < 0 || weight <= 0 { return 0, 0, make([]int, len(items)) }
str := fmt.Sprintf("%d,%d", weight, pos) if s, ok := cache[str]; ok { return s.v, s.w, s.qty }
best_v, best_i, best_w, best_sol := 0, 0, 0, []int(nil)
for i := 0; i * items[pos].weight <= weight && i <= items[pos].qty; i++ { v, w, sol := choose(weight - i * items[pos].weight, pos - 1, cache) v += i * items[pos].value if v > best_v { best_i, best_v, best_w, best_sol = i, v, w, sol } }
taken := make([]int, len(items)) copy(taken, best_sol) taken[pos] = best_i v, w := best_v, best_w + best_i * items[pos].weight
cache[str] = &Solution{v, w, taken} return v, w, taken }
func main() { v, w, s := choose(400, len(items) - 1, make(map[string]*Solution))
fmt.Println("Taking:") for i, t := range s { if t > 0 { fmt.Printf(" %d of %d %s\n", t, items[i].qty, items[i].name) } } fmt.Printf("Value: %d; weight: %d\n", v, w) }</lang>
- Output:
Taking: 1 of 1 map 1 of 1 compass 1 of 2 water 2 of 2 glucose 3 of 3 banana 1 of 1 cheese 1 of 1 suntancream 1 of 1 w-overclothes 1 of 1 note-case 1 of 1 sunglasses 1 of 1 socks Value: 1010; weight: 396
Groovy
Solution: dynamic programming <lang groovy>def totalWeight = { list -> list.collect{ it.item.weight * it.count }.sum() } def totalValue = { list -> list.collect{ it.item.value * it.count }.sum() }
def knapsackBounded = { possibleItems ->
def n = possibleItems.size()
def m = (0..n).collect{ i -> (0..400).collect{ w -> []} }
(1..400).each { w ->
(1..n).each { i ->
def item = possibleItems[i-1]
def wi = item.weight, pi = item.pieces
def bi = [w.intdiv(wi),pi].min()
m[i][w] = (0..bi).collect{ count ->
m[i-1][w - wi * count] + item:item, count:count
}.max(totalValue).findAll{ it.count }
}
}
m[n][400]
}</lang> Test: <lang groovy>def items = [
[name:"map", weight: 9, value:150, pieces:1],
[name:"compass", weight: 13, value: 35, pieces:1],
[name:"water", weight:153, value:200, pieces:2],
[name:"sandwich", weight: 50, value: 60, pieces:2],
[name:"glucose", weight: 15, value: 60, pieces:2],
[name:"tin", weight: 68, value: 45, pieces:3],
[name:"banana", weight: 27, value: 60, pieces:3],
[name:"apple", weight: 39, value: 40, pieces:3],
[name:"cheese", weight: 23, value: 30, pieces:1],
[name:"beer", weight: 52, value: 10, pieces:3],
[name:"suntan cream", weight: 11, value: 70, pieces:1],
[name:"camera", weight: 32, value: 30, pieces:1],
[name:"t-shirt", weight: 24, value: 15, pieces:2],
[name:"trousers", weight: 48, value: 10, pieces:2],
[name:"umbrella", weight: 73, value: 40, pieces:1],
[name:"waterproof trousers", weight: 42, value: 70, pieces:1],
[name:"waterproof overclothes", weight: 43, value: 75, pieces:1],
[name:"note-case", weight: 22, value: 80, pieces:1],
[name:"sunglasses", weight: 7, value: 20, pieces:1],
[name:"towel", weight: 18, value: 12, pieces:2],
[name:"socks", weight: 4, value: 50, pieces:1],
[name:"book", weight: 30, value: 10, pieces:2],
]
def start = System.currentTimeMillis() def packingList = knapsackBounded(items) def elapsed = System.currentTimeMillis() - start
println "Elapsed Time: ${elapsed/1000.0} s" println "Total Weight: ${totalWeight(packingList)}" println " Total Value: ${totalValue(packingList)}" packingList.each {
printf (' item: %-22s weight:%4d value:%4d count:%2d\n',
it.item.name, it.item.weight, it.item.value, it.count)
}</lang>
- Output:
Elapsed Time: 0.603 s Total Weight: 396 Total Value: 1010 item: map weight: 9 value: 150 count: 1 item: compass weight: 13 value: 35 count: 1 item: water weight: 153 value: 200 count: 1 item: glucose weight: 15 value: 60 count: 2 item: banana weight: 27 value: 60 count: 3 item: cheese weight: 23 value: 30 count: 1 item: suntan cream weight: 11 value: 70 count: 1 item: waterproof overclothes weight: 43 value: 75 count: 1 item: note-case weight: 22 value: 80 count: 1 item: sunglasses weight: 7 value: 20 count: 1 item: socks weight: 4 value: 50 count: 1
Haskell
Directly lifted from 1-0 problem: <lang haskell>inv = [("map",9,150,1), ("compass",13,35,1), ("water",153,200,2), ("sandwich",50,60,2), ("glucose",15,60,2), ("tin",68,45,3), ("banana",27,60,3), ("apple",39,40,3), ("cheese",23,30,1), ("beer",52,10,3), ("cream",11,70,1), ("camera",32,30,1), -- what to do if we end up taking one trouser? ("tshirt",24,15,2), ("trousers",48,10,2), ("umbrella",73,40,1), ("wtrousers",42,70,1), ("woverclothes",43,75,1), ("notecase",22,80,1), ("sunglasses",7,20,1), ("towel",18,12,2), ("socks",4,50,1), ("book",30,10,2)]
knapsack items cap = (value, taken) where (value, lst) = foldl addItem (repeat (0,[])) items !! cap taken = filter (\x -> snd x > 0) lst addItem c (name, w, v, cnt) = map f predecessors where
-- predessors is a list which, for each item of c, is a list of
-- the item and all the items a multiple of w places before it
predecessors = map (:[]) ys ++ zipWith (:) zs predecessors
(ys, zs) = splitAt w c
f = maximum . zipWith (\i w -> prepend (i*v, (name, i)) w) [0..cnt]
prepend (v,x) (v2,xs) = (v+v2, x:xs)
main = print $ knapsack inv 400</lang>
- Output:
(1010,[("socks",1),("sunglasses",1),("notecase",1),("woverclothes",1),("cream",1),("cheese",1),("banana",3),("glucose",2),("water",1),("compass",1),("map",1)])
Since list access is linear, the above is actually not very good for large problem sizes. It's much better to use some constant-time lookup structure for cache (same output): <lang haskell>import Data.Array
-- snipped the item list; use the one from above knapsack items cap = (solu items) ! cap where solu = foldr f (listArray (0,cap) (repeat (0,[]))) f (name,w,v,cnt) ss = listArray (0,cap) $ map optimal [0..] where optimal ww = maximum $ (ss!ww):[prepend (v*i,(name,i)) (ss!(ww - i*w)) | i <- [1..cnt], i*w < ww] prepend (x,n) (y,s) = (x+y,n:s)
main = do print $ knapsack inv 400</lang>
J
Brute force solution: <lang j>'names numbers'=:|:".;._2]0 :0
'map'; 9 150 1 'compass'; 13 35 1 'water'; 153 200 2 'sandwich'; 50 60 2 'glucose'; 15 60 2 'tin'; 68 45 3 'banana'; 27 60 3 'apple'; 39 40 3 'cheese'; 23 30 1 'beer'; 52 10 3 'suntan cream'; 11 70 1 'camera'; 32 30 1 'T-shirt'; 24 15 2 'trousers'; 48 10 2 'umbrella'; 73 40 1 'waterproof trousers'; 42 70 1 'waterproof overclothes'; 43 75 1 'note-case'; 22 80 1 'sunglasses'; 7 20 1 'towel'; 18 12 2 'socks'; 4 50 1 'book'; 30 10 2
)
'weights values pieces'=:|:numbers decode=: (pieces+1)&#:
pickBest=:4 :0
NB. given a list of options, return the best option(s) n=. decode y weight=. n+/ .*weights value=. (x >: weight) * n+/ .*values (value = >./value)#y
)
bestCombo=:3 :0
limit=. */pieces+1
i=. 0
step=. 1e6
best=.
while.i<limit do.
best=. 400 pickBest best,(#~ limit&>)i+i.step
i=. i+step
end.
best
)
bestCombo
978832641</lang> Interpretation of answer: <lang j> decode 978832641 1 1 1 0 2 0 3 0 1 0 1 0 0 0 0 0 1 1 1 0 1 0
(0<decode 978832641) # (":,.decode 978832641),.' ',.names
1 map 1 compass 1 water 2 glucose 3 banana 1 cheese 1 suntan cream 1 waterproof overclothes 1 note-case 1 sunglasses 1 socks
weights +/ .* decode 978832641
396
values +/ .* decode 978832641
1010</lang> Dynamic programming solution (faster): <lang j>dyn=:3 :0
m=. 0$~1+400,+/pieces NB. maximum value cache
b=. m NB. best choice cache
opts=.+/\0,pieces NB. distinct item counts before each piece
P=. */\1+0,pieces NB. distinct possibilities before each piece
for_w.1+i.400 do.
for_j.i.#pieces do.
n=. i.1+j{pieces NB. possible counts for this piece
W=. n*j{weights NB. how much they weigh
s=. w>:W NB. permissible options
v=. s*n*j{values NB. consequent values
base=. j{opts NB. base index for these options
I=. <"1 w,.n+base NB. consequent indices
i0=. <w,base NB. status quo index
iN=. <"1 (w-s*W),.base NB. predecessor indices
M=. >./\(m{~i0)>.v+m{~iN NB. consequent maximum values
C=. (n*j{P)+b{~iN NB. unique encoding for each option
B=. >./\(b{~i0)>. C * 2 ~:/\ 0,M NB. best options, so far
m=. M I} m NB. update with newly computed maxima
b=. B I} b NB. same for best choice
end.
end.
|.(1+|.pieces)#:{:{:b
)
dyn
1 1 1 0 2 0 3 0 1 0 1 0 0 0 0 0 1 1 1 0 1 0</lang> Note: the brute force approach would return multiple "best answers" if more than one combination of choices would satisfy the "best" constraint. The dynamic approach arbitrarily picks one of those choices. That said, with this particular choice of item weights and values, this is an irrelevant distinction.
Java
General dynamic solution after wikipedia. The solution extends the method of Knapsack problem/0-1#Java . <lang java>package hu.pj.alg.test;
import hu.pj.alg.BoundedKnapsack; import hu.pj.obj.Item; import java.util.*; import java.text.*;
public class BoundedKnapsackForTourists {
public BoundedKnapsackForTourists() {
BoundedKnapsack bok = new BoundedKnapsack(400); // 400 dkg = 400 dag = 4 kg
// making the list of items that you want to bring
bok.add("map", 9, 150, 1);
bok.add("compass", 13, 35, 1);
bok.add("water", 153, 200, 3);
bok.add("sandwich", 50, 60, 2);
bok.add("glucose", 15, 60, 2);
bok.add("tin", 68, 45, 3);
bok.add("banana", 27, 60, 3);
bok.add("apple", 39, 40, 3);
bok.add("cheese", 23, 30, 1);
bok.add("beer", 52, 10, 3);
bok.add("suntan cream", 11, 70, 1);
bok.add("camera", 32, 30, 1);
bok.add("t-shirt", 24, 15, 2);
bok.add("trousers", 48, 10, 2);
bok.add("umbrella", 73, 40, 1);
bok.add("waterproof trousers", 42, 70, 1);
bok.add("waterproof overclothes", 43, 75, 1);
bok.add("note-case", 22, 80, 1);
bok.add("sunglasses", 7, 20, 1);
bok.add("towel", 18, 12, 2);
bok.add("socks", 4, 50, 1);
bok.add("book", 30, 10, 2);
// calculate the solution:
List<Item> itemList = bok.calcSolution();
// write out the solution in the standard output
if (bok.isCalculated()) {
NumberFormat nf = NumberFormat.getInstance();
System.out.println(
"Maximal weight = " +
nf.format(bok.getMaxWeight() / 100.0) + " kg"
);
System.out.println(
"Total weight of solution = " +
nf.format(bok.getSolutionWeight() / 100.0) + " kg"
);
System.out.println(
"Total value = " +
bok.getProfit()
);
System.out.println();
System.out.println(
"You can carry te following materials " +
"in the knapsack:"
);
for (Item item : itemList) {
if (item.getInKnapsack() > 0) {
System.out.format(
"%1$-10s %2$-23s %3$-3s %4$-5s %5$-15s \n",
item.getInKnapsack() + " unit(s) ",
item.getName(),
item.getInKnapsack() * item.getWeight(), "dag ",
"(value = " + item.getInKnapsack() * item.getValue() + ")"
);
}
}
} else {
System.out.println(
"The problem is not solved. " +
"Maybe you gave wrong data."
);
}
}
public static void main(String[] args) {
new BoundedKnapsackForTourists();
}
} // class</lang> <lang java>package hu.pj.alg;
import hu.pj.obj.Item; import java.util.*;
public class BoundedKnapsack extends ZeroOneKnapsack {
public BoundedKnapsack() {}
public BoundedKnapsack(int _maxWeight) {
setMaxWeight(_maxWeight);
}
public BoundedKnapsack(List<Item> _itemList) {
setItemList(_itemList);
}
public BoundedKnapsack(List<Item> _itemList, int _maxWeight) {
setItemList(_itemList);
setMaxWeight(_maxWeight);
}
@Override
public List<Item> calcSolution() {
int n = itemList.size();
// add items to the list, if bounding > 1
for (int i = 0; i < n; i++) {
Item item = itemList.get(i);
if (item.getBounding() > 1) {
for (int j = 1; j < item.getBounding(); j++) {
add(item.getName(), item.getWeight(), item.getValue());
}
}
}
super.calcSolution();
// delete the added items, and increase the original items
while (itemList.size() > n) {
Item lastItem = itemList.get(itemList.size() - 1);
if (lastItem.getInKnapsack() == 1) {
for (int i = 0; i < n; i++) {
Item iH = itemList.get(i);
if (lastItem.getName().equals(iH.getName())) {
iH.setInKnapsack(1 + iH.getInKnapsack());
break;
}
}
}
itemList.remove(itemList.size() - 1);
}
return itemList; }
// add an item to the item list
public void add(String name, int weight, int value, int bounding) {
if (name.equals(""))
name = "" + (itemList.size() + 1);
itemList.add(new Item(name, weight, value, bounding));
setInitialStateForCalculation();
}
} // class</lang> <lang java>package hu.pj.alg;
import hu.pj.obj.Item; import java.util.*;
public class ZeroOneKnapsack {
protected List<Item> itemList = new ArrayList<Item>(); protected int maxWeight = 0; protected int solutionWeight = 0; protected int profit = 0; protected boolean calculated = false;
public ZeroOneKnapsack() {}
public ZeroOneKnapsack(int _maxWeight) {
setMaxWeight(_maxWeight);
}
public ZeroOneKnapsack(List<Item> _itemList) {
setItemList(_itemList);
}
public ZeroOneKnapsack(List<Item> _itemList, int _maxWeight) {
setItemList(_itemList);
setMaxWeight(_maxWeight);
}
// calculte the solution of 0-1 knapsack problem with dynamic method:
public List<Item> calcSolution() {
int n = itemList.size();
setInitialStateForCalculation();
if (n > 0 && maxWeight > 0) {
List< List<Integer> > c = new ArrayList< List<Integer> >();
List<Integer> curr = new ArrayList<Integer>();
c.add(curr);
for (int j = 0; j <= maxWeight; j++)
curr.add(0);
for (int i = 1; i <= n; i++) {
List<Integer> prev = curr;
c.add(curr = new ArrayList<Integer>());
for (int j = 0; j <= maxWeight; j++) {
if (j > 0) {
int wH = itemList.get(i-1).getWeight();
curr.add(
(wH > j)
?
prev.get(j)
:
Math.max(
prev.get(j),
itemList.get(i-1).getValue() + prev.get(j-wH)
)
);
} else {
curr.add(0);
}
} // for (j...)
} // for (i...)
profit = curr.get(maxWeight);
for (int i = n, j = maxWeight; i > 0 && j >= 0; i--) {
int tempI = c.get(i).get(j);
int tempI_1 = c.get(i-1).get(j);
if (
(i == 0 && tempI > 0)
||
(i > 0 && tempI != tempI_1)
)
{
Item iH = itemList.get(i-1);
int wH = iH.getWeight();
iH.setInKnapsack(1);
j -= wH;
solutionWeight += wH;
}
} // for()
calculated = true;
} // if()
return itemList;
}
// add an item to the item list
public void add(String name, int weight, int value) {
if (name.equals(""))
name = "" + (itemList.size() + 1);
itemList.add(new Item(name, weight, value));
setInitialStateForCalculation();
}
// add an item to the item list
public void add(int weight, int value) {
add("", weight, value); // the name will be "itemList.size() + 1"!
}
// remove an item from the item list
public void remove(String name) {
for (Iterator<Item> it = itemList.iterator(); it.hasNext(); ) {
if (name.equals(it.next().getName())) {
it.remove();
}
}
setInitialStateForCalculation();
}
// remove all items from the item list
public void removeAllItems() {
itemList.clear();
setInitialStateForCalculation();
}
public int getProfit() {
if (!calculated)
calcSolution();
return profit;
}
public int getSolutionWeight() {return solutionWeight;}
public boolean isCalculated() {return calculated;}
public int getMaxWeight() {return maxWeight;}
public void setMaxWeight(int _maxWeight) {
maxWeight = Math.max(_maxWeight, 0);
}
public void setItemList(List<Item> _itemList) {
if (_itemList != null) {
itemList = _itemList;
for (Item item : _itemList) {
item.checkMembers();
}
}
}
// set the member with name "inKnapsack" by all items:
private void setInKnapsackByAll(int inKnapsack) {
for (Item item : itemList)
if (inKnapsack > 0)
item.setInKnapsack(1);
else
item.setInKnapsack(0);
}
// set the data members of class in the state of starting the calculation:
protected void setInitialStateForCalculation() {
setInKnapsackByAll(0);
calculated = false;
profit = 0;
solutionWeight = 0;
}
} // class</lang> <lang java>package hu.pj.obj;
public class Item {
protected String name = ""; protected int weight = 0; protected int value = 0; protected int bounding = 1; // the maximal limit of item's pieces protected int inKnapsack = 0; // the pieces of item in solution
public Item() {}
public Item(Item item) {
setName(item.name);
setWeight(item.weight);
setValue(item.value);
setBounding(item.bounding);
}
public Item(int _weight, int _value) {
setWeight(_weight);
setValue(_value);
}
public Item(int _weight, int _value, int _bounding) {
setWeight(_weight);
setValue(_value);
setBounding(_bounding);
}
public Item(String _name, int _weight, int _value) {
setName(_name);
setWeight(_weight);
setValue(_value);
}
public Item(String _name, int _weight, int _value, int _bounding) {
setName(_name);
setWeight(_weight);
setValue(_value);
setBounding(_bounding);
}
public void setName(String _name) {name = _name;}
public void setWeight(int _weight) {weight = Math.max(_weight, 0);}
public void setValue(int _value) {value = Math.max(_value, 0);}
public void setInKnapsack(int _inKnapsack) {
inKnapsack = Math.min(getBounding(), Math.max(_inKnapsack, 0));
}
public void setBounding(int _bounding) {
bounding = Math.max(_bounding, 0);
if (bounding == 0)
inKnapsack = 0;
}
public void checkMembers() {
setWeight(weight);
setValue(value);
setBounding(bounding);
setInKnapsack(inKnapsack);
}
public String getName() {return name;}
public int getWeight() {return weight;}
public int getValue() {return value;}
public int getInKnapsack() {return inKnapsack;}
public int getBounding() {return bounding;}
} // class</lang>
- Output:
Maximal weight = 4 kg Total weight of solution = 3,96 kg Total value = 1010 You can carry te following materials in the knapsack: 1 unit(s) map 9 dag (value = 150) 1 unit(s) compass 13 dag (value = 35) 1 unit(s) water 153 dag (value = 200) 2 unit(s) glucose 30 dag (value = 120) 3 unit(s) banana 81 dag (value = 180) 1 unit(s) cheese 23 dag (value = 30) 1 unit(s) suntan cream 11 dag (value = 70) 1 unit(s) waterproof overclothes 43 dag (value = 75) 1 unit(s) note-case 22 dag (value = 80) 1 unit(s) sunglasses 7 dag (value = 20) 1 unit(s) socks 4 dag (value = 50)
JavaScript
Based on the (dynamic) J implementation. Expressed as an htm page: <lang javascript><html><head><title></title></head><body></body></html>
<script type="text/javascript"> var data= [
{name: 'map', weight: 9, value:150, pieces:1},
{name: 'compass', weight: 13, value: 35, pieces:1},
{name: 'water', weight:153, value:200, pieces:2},
{name: 'sandwich', weight: 50, value: 60, pieces:2},
{name: 'glucose', weight: 15, value: 60, pieces:2},
{name: 'tin', weight: 68, value: 45, pieces:3},
{name: 'banana', weight: 27, value: 60, pieces:3},
{name: 'apple', weight: 39, value: 40, pieces:3},
{name: 'cheese', weight: 23, value: 30, pieces:1},
{name: 'beer', weight: 52, value: 10, pieces:3},
{name: 'suntan, cream', weight: 11, value: 70, pieces:1},
{name: 'camera', weight: 32, value: 30, pieces:1},
{name: 'T-shirt', weight: 24, value: 15, pieces:2},
{name: 'trousers', weight: 48, value: 10, pieces:2},
{name: 'umbrella', weight: 73, value: 40, pieces:1},
{name: 'waterproof, trousers', weight: 42, value: 70, pieces:1},
{name: 'waterproof, overclothes',weight: 43, value: 75, pieces:1},
{name: 'note-case', weight: 22, value: 80, pieces:1},
{name: 'sunglasses', weight: 7, value: 20, pieces:1},
{name: 'towel', weight: 18, value: 12, pieces:2},
{name: 'socks', weight: 4, value: 50, pieces:1},
{name: 'book', weight: 30, value: 10, pieces:2}
];
function findBestPack() { var m= 0; // maximum pack value found so far var b= 0; // best combination found so far var opts= [0]; // item index for 0 of item 0 var P= [1]; // item encoding for 0 of item 0 var choose= 0; for (var j= 0; j<data.length; j++) { opts[j+1]= opts[j]+data[j].pieces; // item index for 0 of item j+1 P[j+1]= P[j]*(1+data[j].pieces); // item encoding for 0 of item j+1 } for (var j= 0; j<opts[data.length]; j++) { m[0][j+1]= b[0][j+1]= 0; // best values and combos for empty pack: nothing } for (var w=1; w<=400; w++) { m[w]= [0]; b[w]= [0]; for (var j=0; j<data.length; j++) { var N= data[j].pieces; // how many of these can we have? var base= opts[j]; // what is the item index for 0 of these? for (var n= 1; n<=N; n++) { var W= n*data[j].weight; // how much do these items weigh? var s= w>=W ?1 :0; // can we carry this many? var v= s*n*data[j].value; // how much are they worth? var I= base+n; // what is the item number for this many? var wN= w-s*W; // how much other stuff can we be carrying? var C= n*P[j] + b[wN][base]; // encoded combination m[w][I]= Math.max(m[w][I-1], v+m[wN][base]); // best value choose= b[w][I]= m[w][I]>m[w][I-1] ?C :b[w][I-1]; } } } var best= []; for (var j= data.length-1; j>=0; j--) { best[j]= Math.floor(choose/P[j]); choose-= best[j]*P[j]; }
var out='
';var wgt= 0; var val= 0; for (var i= 0; i<best.length; i++) { if (0==best[i]) continue;
out+=''wgt+= best[i]*data[i].weight; val+= best[i]*data[i].value; }
out+= '| Count | Item | unit weight | unit value |
|---|---|---|---|
| '+best[i]+' | '+data[i].name+' | '+data[i].weight+' | '+data[i].value+' |
Total weight: '+wgt;
out+= '
Total value: '+val;
document.body.innerHTML= out;
}
findBestPack();
</script></lang>
This will generate (translating html to mediawiki markup):
| Count | Item | unit weight | unit value |
|---|---|---|---|
| 1 | map | 9 | 150 |
| 1 | compass | 13 | 35 |
| 1 | water | 153 | 200 |
| 2 | glucose | 15 | 60 |
| 3 | banana | 27 | 60 |
| 1 | cheese | 23 | 30 |
| 1 | suntan, cream | 11 | 70 |
| 1 | waterproof, overclothes | 43 | 75 |
| 1 | note-case | 22 | 80 |
| 1 | sunglasses | 7 | 20 |
| 1 | socks | 4 | 50 |
Total weight: 396
Total value: 1010
Mathprog
<lang mathprog>/*Knapsack
This model finds the integer optimal packing of a knapsack Nigel_Galloway January 9th., 2012
- /
set Items; param weight{t in Items}; param value{t in Items}; param quantity{t in Items};
var take{t in Items}, integer, >=0, <=quantity[t];
knap_weight : sum{t in Items} take[t] * weight[t] <= 400;
maximize knap_value: sum{t in Items} take[t] * value[t];
data;
param : Items : weight value quantity :=
map 9 150 1
compass 13 35 1
water 153 200 2
sandwich 50 60 2
glucose 15 60 2
tin 68 45 3
banana 27 60 3
apple 39 40 3
cheese 23 30 1
beer 52 10 3
suntancream 11 70 1
camera 32 30 1
T-shirt 24 15 2
trousers 48 10 2
umbrella 73 40 1
w-trousers 42 70 1
w-overclothes 43 75 1
note-case 22 80 1
sunglasses 7 20 1
towel 18 12 2
socks 4 50 1
book 30 10 2
end;</lang>
The solution produced using glpk is here: Knapsack problem/Bounded/Mathprog
lpsolve may also be used. The result may be found here: File:Knap_objective.png
The constraints may be found here: File:Knap_constraint.png
OOCalc
OpenOffice.org Calc has (several) linear solvers. To solve this task, first copy in the table from the task description, then add the extra columns:
- Number: (How many chosen)
- weight of n
- value of n
Add a TOTALS row to sum the weight/value of n.
The sheet should then look like this:
table pre solving
Open the "Tools->Solver..." menu item and fill in the following items:
- Target Cell: $H$27
- Optimise result to: maximum
- By Changing cells: $F$5:$F$26
- Limiting conditions:
- $F$5:$F$26 <= $E$5:$E$26
- $G$27 <= 400
solver menu
- Options... (opens a separate popup window, then continue)
- Solver engine: OpenOffice.org Linear Solver
- Settings:
- Assume variables as integer: True
- Assume variables as non-negative: True
- Epsilon level: 0
- Limit branch-and-bound depth: True
- Solving time limit (seconds): 100
solver popup options menu
OK the solver options window leaving the Solver window open, then select solve to produce in seconds:
Table solved
OxygenBasic
<lang oxygenbasic> type KnapSackItem string name,sys dag,value,tag
KnapSackItem it[100]
sys dmax=400 sys items=22
it=>
"map", 9, 150, 0, "compass", 13, 35, 0, "water", 153, 200, 0, "sandwich", 50, 160, 0, "glucose", 15, 60, 0, "tin", 68, 45, 0, "banana", 27, 60, 0, "apple", 39, 40, 0, "cheese", 23, 30, 0, "beer", 52, 10, 0, "suntan cream", 11, 70, 0, "camera", 32, 30, 0, "T-shirt", 24, 15, 0, "trousers", 48, 10, 0, "umbrella", 73, 40, 0, "waterproof trousers", 42, 70, 0, "waterproof overclothes",43, 75, 0, "note-case", 22, 80, 0, "sunglasses", 7, 20, 0, "towel", 18, 12, 0, "socks", 4, 50, 0, "book", 30, 10, 0
tot=0 for i=1 to items
tot+=it(i).dag
next xs=tot-dmax
'REMOVE LOWEST PRIORITY ITEMS TILL XS<=0
cr=chr(13)+chr(10) tab=chr(9) pr="remove: " cr c=0
do
v=1e9
w=0
k=0
'
'FIND NEXT LEAST VALUE ITEM
'
for i=1 to items
if it[i].tag=0
'w=it[i].value 'TEST PRIORITY ONLY
w=1000*it[i].value/it[i].dag 'TEST PRIORIT/WEIGHT VALUE
if w<v then v=w : k=i
end if
next
'
'LOG AND REMOVE FROM LIST
'
if k
xs-=it[k].dag 'deduct from excess weight
it[k].tag=1
pr+=it(k).name tab it(k).dag tab it(k).value cr
if xs<=0 then exit do 'Weight within dmax
end if
c++
if c>=items then exit do
end do ' pr+=cr "Knapsack contents: " cr ' for i=1 to items
if it(i).tag=0 pr+=it(i).name tab it(i).dag tab it(i).value cr end if
next
'TRY FITTING IN LOWER PRIORITY ITEMS
av=-xs
for i=1 to items
if it[i].tag
if av-it[i].dag > 0 then
pr+="Can include: " it(i).name tab it(i).dag tab it(i).value cr
av-=it[i].dag
end if
end if
next pr+=cr "Weight: " dmax+xs 'putfile "s.txt",pr print pr 'Knapsack contents: 'map 9 150 'compass 13 35 'water 153 200 'sandwich 50 160 'glucose 15 60 'banana 27 60 'suntan cream 11 70 'waterproof trousers 42 70 'waterproof overclothes 43 75 'note-case 22 80 'sunglasses 7 20 'socks 4 50 ' 'Weight: 396 </lang>
Oz
Using constraint programming. <lang oz>declare
%% maps items to tuples of
%% Weight(hectogram), Value and available Pieces
Problem = knapsack('map':9#150#1
'compass':13#35#1
'water':153#200#2
'sandwich':50#60#2
'glucose':15#60#2
'tin':68#45#3
'banana':27#60#3
'apple':39#40#3
'cheese':23#30#1
'beer':52#10#3
'suntan cream':11#70#1
'camera':32#30#1
't-shirt':24#15#2
'trousers':48#10#2
'umbrella':73#40#1
'waterproof trousers':42#70#1
'waterproof overclothes':43#75#1
'note-case':22#80#1
'sunglasses':7#20#1
'towel':18#12#2
'socks':4#50#1
'book':30#10#2
)
%% item -> Weight
Weights = {Record.map Problem fun {$ X} X.1 end}
%% item -> Value
Values = {Record.map Problem fun {$ X} X.2 end}
proc {Knapsack Solution}
%% a solution maps items to finite domain variables
%% whose maximum values depend on the item type
Solution = {Record.map Problem fun {$ _#_#Max} {FD.int 0#Max} end}
%% no more than 400 hectograms
{FD.sumC Weights Solution '=<:' 400}
%% search through valid solutions
{FD.distribute naive Solution}
end
proc {PropagateLargerValue Old New}
%% propagate that new solutions must yield a higher value
%% than previously found solutions (essential for performance)
{FD.sumC Values New '>:' {Value Old}}
end
fun {Value Candidate}
{Record.foldL {Record.zip Candidate Values Number.'*'} Number.'+' 0}
end
fun {Weight Candidate}
{Record.foldL {Record.zip Candidate Weights Number.'*'} Number.'+' 0}
end
[Best] = {SearchBest Knapsack PropagateLargerValue}
in
{System.showInfo "Items: "}
{Record.forAllInd Best
proc {$ I V}
if V > 0 then
{System.showInfo I#": "#V}
end
end
}
{System.printInfo "\n"}
{System.showInfo "total value: "#{Value Best}}
{System.showInfo "total weight: "#{Weight Best}}</lang>
- Output:
Items: banana: 3 cheese: 1 compass: 1 glucose: 2 map: 1 note-case: 1 socks: 1 sunglasses: 1 suntan cream: 1 water: 1 waterproof overclothes: 1 total value: 1010 total weight: 396
Takes about 3 seconds on a slow netbook.
Perl
Recursive solution with caching. <lang Perl>#!/usr/bin/perl
use strict;
my $raw = <<'TABLE'; map 9 150 1 compass 13 35 1 water 153 200 2 sandwich 50 60 2 glucose 15 60 2 tin 68 45 3 banana 27 60 3 apple 39 40 3 cheese 23 30 1 beer 52 10 1 suntancream 11 70 1 camera 32 30 1 T-shirt 24 15 2 trousers 48 10 2 umbrella 73 40 1 w_trousers 42 70 1 w_overcoat 43 75 1 note-case 22 80 1 sunglasses 7 20 1 towel 18 12 2 socks 4 50 1 book 30 10 2 TABLE
my @items; for (split "\n", $raw) {
my @x = split /\s+/;
push @items, { name => $x[0], weight => $x[1], value => $x[2], quant => $x[3], } }
my $max_weight = 400;
my %cache; sub pick { my ($weight, $pos) = @_; if ($pos < 0 or $weight <= 0) { return 0, 0, [] }
@{ $cache{$weight, $pos} //= [do{ # odd construct: for caching my $item = $items[$pos]; my ($bv, $bi, $bw, $bp) = (0, 0, 0, []);
for my $i (0 .. $item->{quant}) { last if $i * $item->{weight} > $weight; my ($v, $w, $p) = pick($weight - $i * $item->{weight}, $pos - 1); next if ($v += $i * $item->{value}) <= $bv;
($bv, $bi, $bw, $bp) = ($v, $i, $w, $p); }
my @picked = ( @$bp, $bi ); $bv, $bw + $bi * $item->{weight}, \@picked }]} }
my ($v, $w, $p) = pick(400, $#items); for (0 .. $#$p) { if ($p->[$_] > 0) { print "$p->[$_] of $items[$_]{name}\n"; } } print "Value: $v; Weight: $w\n";</lang>
- Output:
1 of map 1 of compass 1 of water 2 of glucose 3 of banana 1 of cheese 1 of suntancream 1 of w_overcoat 1 of note-case 1 of sunglasses 1 of socks Value: 1010; Weight: 396
Perl 6
<lang perl6>my class KnapsackItem { has $.name; has $.weight; has $.unit; }
multi sub pokem ([], $, $v = 0) { $v } multi sub pokem ([$, *@], 0, $v = 0) { $v } multi sub pokem ([$i, *@rest], $w, $v = 0) {
my $key = "{+@rest} $w $v";
(state %cache){$key} or do {
my @skip = pokem @rest, $w, $v;
if $w >= $i.weight { # next one fits
my @put = pokem @rest, $w - $i.weight, $v + $i.unit;
return (%cache{$key} = @put, $i.name).list if @put[0] > @skip[0];
}
return (%cache{$key} = @skip).list;
}
}
my $MAX_WEIGHT = 400; my @table = map -> $name, $weight, $unit, $count {
KnapsackItem.new( :$name, :$weight, :$unit ) xx $count;
},
'map', 9, 150, 1,
'compass', 13, 35, 1,
'water', 153, 200, 2,
'sandwich', 50, 60, 2,
'glucose', 15, 60, 2,
'tin', 68, 45, 3,
'banana', 27, 60, 3,
'apple', 39, 40, 3,
'cheese', 23, 30, 1,
'beer', 52, 10, 3,
'suntan cream', 11, 70, 1,
'camera', 32, 30, 1,
'T-shirt', 24, 15, 2,
'trousers', 48, 10, 2,
'umbrella', 73, 40, 1,
'waterproof trousers', 42, 70, 1,
'waterproof overclothes', 43, 75, 1,
'note-case', 22, 80, 1,
'sunglasses', 7, 20, 1,
'towel', 18, 12, 2,
'socks', 4, 50, 1,
'book', 30, 10, 2,
;
my ($value, @result) = pokem @table, $MAX_WEIGHT;
(my %hash){$_}++ for @result;
say "Value = $value"; say "Tourist put in the bag:"; say " # ITEM"; for %hash.kv -> $item, $number {
say " $number $item";
}</lang>
- Output:
Value = 1010 Tourist put in the bag: # ITEM 1 socks 1 sunglasses 1 note-case 1 waterproof overclothes 1 suntan cream 1 cheese 3 banana 2 glucose 1 water 1 compass 1 map
PicoLisp
<lang PicoLisp>(de *Items
("map" 9 150 1) ("compass" 13 35 1)
("water" 153 200 3) ("sandwich" 50 60 2)
("glucose" 15 60 2) ("tin" 68 45 3)
("banana" 27 60 3) ("apple" 39 40 3)
("cheese" 23 30 1) ("beer" 52 10 3)
("suntan cream" 11 70 1) ("camera" 32 30 1)
("t-shirt" 24 15 2) ("trousers" 48 10 2)
("umbrella" 73 40 1) ("waterproof trousers" 42 70 1)
("waterproof overclothes" 43 75 1) ("note-case" 22 80 1)
("sunglasses" 7 20 1) ("towel" 18 12 2)
("socks" 4 50 1) ("book" 30 10 2) )
- Dynamic programming solution
(de knapsack (Lst W)
(when Lst
(cache '*KnapCache (pack (length Lst) ":" W)
(let X (knapsack (cdr Lst) W)
(if (ge0 (- W (cadar Lst)))
(let Y (cons (car Lst) (knapsack (cdr Lst) @))
(if (> (sum caddr X) (sum caddr Y)) X Y) )
X ) ) ) ) )
(let K
(knapsack
(mapcan # Expand multiple items
'((X) (need (cadddr X) NIL X))
*Items )
400 )
(for I K
(apply tab I (3 -24 6 6) NIL) )
(tab (27 6 6) NIL (sum cadr K) (sum caddr K)) )</lang>
- Output:
map 9 150
compass 13 35
water 153 200
glucose 15 60
glucose 15 60
banana 27 60
banana 27 60
banana 27 60
cheese 23 30
suntan cream 11 70
waterproof overclothes 43 75
note-case 22 80
sunglasses 7 20
socks 4 50
396 1010
Prolog
Library clpfd
Library clpfd is written by Markus Triska. Takes about 3 minutes to compute the best solution. <lang Prolog>:- use_module(library(clpfd)).
% tuples (name, weights, value, nb pieces). knapsack :- L = [( map, 9, 150, 1), ( compass, 13, 35, 1), ( water, 153, 200, 2), ( sandwich, 50, 60, 2), ( glucose, 15, 60, 2), ( tin, 68, 45, 3), ( banana, 27, 60, 3), ( apple, 39, 40, 3), ( cheese, 23, 30, 1), ( beer, 52, 10, 3), ( 'suntan cream', 11, 70, 1), ( camera, 32, 30, 1), ( 'T-shirt', 24, 15, 2), ( trousers, 48, 10, 2), ( umbrella, 73, 40, 1), ( 'waterproof trousers', 42, 70, 1), ( 'waterproof overclothes', 43, 75, 1), ( 'note-case', 22, 80, 1), ( sunglasses, 7, 20, 1), ( towel, 18, 12, 2), ( socks, 4, 50, 1), ( book, 30, 10, 2)],
% R is the list of the numbers of each items % these numbers are between 0 and the 4th value of the tuples of the items maplist(create_lists,L, R, LW, LV), sum(LW, #=<, 400), sum(LV, #=, VM),
% to have statistics on the resolution of the problem. time(labeling([max(VM)], R)), sum(LW, #=, WM),
%% displayinf of the results. compute_lenword(L, 0, Len), sformat(A1, '~~w~~t~~~w|', [Len]), sformat(A2, '~~t~~w~~~w|', [4]), sformat(A3, '~~t~~w~~~w|', [5]), print_results(A1,A2,A3, L, R, WM, VM).
create_lists((_, W, V, N), C, LW, LV) :-
C in 0..N,
LW #= C * W,
LV #= C * V.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % compute_lenword([], N, N). compute_lenword([(Name, _, _, _)|T], N, NF):- atom_length(Name, L), ( L > N -> N1 = L; N1 = N), compute_lenword(T, N1, NF).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % print_results(A1,A2,A3, [], [], WM, WR) :- sformat(W0, '~w ', [' ']), sformat(W1, A1, [' ']), sformat(W2, A2, [WM]), sformat(W3, A3, [WR]), format('~w~w~w~w~n', [W0,W1,W2,W3]).
print_results(A1,A2,A3, [_H|T], [0|TR], WM, VM) :-
!,
print_results(A1,A2,A3, T, TR, WM, VM).
print_results(A1, A2, A3, [(Name, W, V, _)|T], [N|TR], WM, VM) :- sformat(W0, '~w ', [N]), sformat(W1, A1, [Name]), sformat(W2, A2, [W]), sformat(W3, A3, [V]), format('~w~w~w~w~n', [W0,W1,W2,W3]), print_results(A1, A2, A3, T, TR, WM, VM).</lang>
- Output:
?- knapsack.
% 637,813,025 inferences, 195.641 CPU in 197.203 seconds (99% CPU, 3260126 Lips)
1 map 9 150
1 compass 13 35
1 water 153 200
2 glucose 15 60
3 banana 27 60
1 cheese 23 30
1 suntan cream 11 70
1 waterproof overclothes 43 75
1 note-case 22 80
1 sunglasses 7 20
1 socks 4 50
396 1010
true
Library simplex
Library simplex is written by Markus Triska. Takes about 10 seconds to compute the best solution. <lang Prolog>:- use_module(library(simplex)). % tuples (name, weights, value, pieces). knapsack :- L = [(map, 9, 150, 1), ( compass, 13, 35, 1), ( water, 153, 200, 2), ( sandwich, 50, 60, 2), ( glucose, 15, 60, 2), ( tin, 68, 45, 3), ( banana, 27, 60, 3), ( apple, 39, 40, 3), ( cheese, 23, 30, 1), ( beer, 52, 10, 3), ( 'suntan cream', 11, 70, 1), ( camera, 32, 30, 1), ( 'T-shirt', 24, 15, 2), ( trousers, 48, 10, 2), ( umbrella, 73, 40, 1), ( 'waterproof trousers', 42, 70, 1), ( 'waterproof overclothes', 43, 75, 1), ( 'note-case', 22, 80, 1), ( sunglasses, 7, 20, 1), ( towel, 18, 12, 2), ( socks, 4, 50, 1), ( book, 30, 10, 2)],
gen_state(S0), length(L, N), numlist(1, N, LN), time(( create_constraint_N(LN, L, S0, S1), maplist(create_constraint_WV, LN, L, LW, LV), constraint(LW =< 400, S1, S2), maximize(LV, S2, S3) )), compute_lenword(L, 0, Len), sformat(A1, '~~w~~t~~~w|', [Len]), sformat(A2, '~~t~~w~~~w|', [4]), sformat(A3, '~~t~~w~~~w|', [5]), print_results(S3, A1,A2,A3, L, LN, 0, 0).
create_constraint_N([], [], S, S).
create_constraint_N([HN|TN], [(_, _, _, Nb) | TL], S1, SF) :- constraint(integral(x(HN)), S1, S2), constraint([x(HN)] =< Nb, S2, S3), constraint([x(HN)] >= 0, S3, S4), create_constraint_N(TN, TL, S4, SF).
create_constraint_WV(N, (_, W, V, _), W * x(N), V * x(N)).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % compute_lenword([], N, N). compute_lenword([(Name, _, _, _)|T], N, NF):- atom_length(Name, L), ( L > N -> N1 = L; N1 = N), compute_lenword(T, N1, NF).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % print_results(_S, A1, A2, A3, [], [], WM, VM) :- sformat(W0, '~w ', [' ']), sformat(W1, A1, [' ']), sformat(W2, A2, [WM]), sformat(W3, A3, [VM]), format('~w~w~w~w~n', [W0, W1,W2,W3]).
print_results(S, A1, A2, A3, [(Name, W, V,_)|T], [N|TN], W1, V1) :-
variable_value(S, x(N), X),
( X = 0 -> W1 = W2, V1 = V2
; sformat(S0, '~w ', [X]),
sformat(S1, A1, [Name]),
sformat(S2, A2, [W]),
sformat(S3, A3, [V]),
format('~w~w~w~w~n', [S0, S1,S2,S3]),
W2 is W1 + X * W,
V2 is V1 + X * V),
print_results(S, A1, A2, A3, T, TN, W2, V2).</lang>
Python
Not as dumb a search over all possible combinations under the maximum allowed weight: <lang python>from itertools import groupby from collections import namedtuple from pprint import pprint as pp
def anyvalidcomb(items, val=0, wt=0):
' All combinations below the maxwt '
if not items:
yield [], val, wt
else:
this, *items = items # car, cdr
for n in range(this.number+1):
v = val + n*this.value
w = wt + n*this.weight
if w > maxwt:
break
for c in anyvalidcomb(items, v, w):
yield [this]*n + c[COMB], c[VAL], c[WT]
maxwt = 400 COMB, VAL, WT = range(3) Item = namedtuple('Items', 'name weight value number') items = [ Item(*x) for x in
(
("map", 9, 150, 1),
("compass", 13, 35, 1),
("water", 153, 200, 3),
("sandwich", 50, 60, 2),
("glucose", 15, 60, 2),
("tin", 68, 45, 3),
("banana", 27, 60, 3),
("apple", 39, 40, 3),
("cheese", 23, 30, 1),
("beer", 52, 10, 3),
("suntan cream", 11, 70, 1),
("camera", 32, 30, 1),
("t-shirt", 24, 15, 2),
("trousers", 48, 10, 2),
("umbrella", 73, 40, 1),
("waterproof trousers", 42, 70, 1),
("waterproof overclothes", 43, 75, 1),
("note-case", 22, 80, 1),
("sunglasses", 7, 20, 1),
("towel", 18, 12, 2),
("socks", 4, 50, 1),
("book", 30, 10, 2),
) ]
bagged = max( anyvalidcomb(items), key=lambda c: (c[VAL], -c[WT])) # max val or min wt if values equal print("Bagged the following %i items\n " % len(bagged[COMB]) +
'\n '.join('%i off: %s' % (len(list(grp)), item.name)
for item,grp in groupby(sorted(bagged[COMB]))))
print("for a total value of %i and a total weight of %i" % bagged[1:])</lang>
- Output:
Bagged the following 14 items 3 off: banana 1 off: cheese 1 off: compass 2 off: glucose 1 off: map 1 off: note-case 1 off: socks 1 off: sunglasses 1 off: suntan cream 1 off: water 1 off: waterproof overclothes for a total value of 1010 and a total weight of 396
Dynamic programming solution
This is much faster. It expands the multiple possible instances of an item into individual instances then applies the zero-one dynamic knapsack solution: <lang python>from itertools import groupby
try:
xrange
except:
xrange = range
maxwt = 400
groupeditems = (
("map", 9, 150, 1),
("compass", 13, 35, 1),
("water", 153, 200, 3),
("sandwich", 50, 60, 2),
("glucose", 15, 60, 2),
("tin", 68, 45, 3),
("banana", 27, 60, 3),
("apple", 39, 40, 3),
("cheese", 23, 30, 1),
("beer", 52, 10, 3),
("suntan cream", 11, 70, 1),
("camera", 32, 30, 1),
("t-shirt", 24, 15, 2),
("trousers", 48, 10, 2),
("umbrella", 73, 40, 1),
("waterproof trousers", 42, 70, 1),
("waterproof overclothes", 43, 75, 1),
("note-case", 22, 80, 1),
("sunglasses", 7, 20, 1),
("towel", 18, 12, 2),
("socks", 4, 50, 1),
("book", 30, 10, 2),
)
items = sum( ([(item, wt, val)]*n for item, wt, val,n in groupeditems), [])
def knapsack01_dp(items, limit):
table = [[0 for w in range(limit + 1)] for j in xrange(len(items) + 1)]
for j in xrange(1, len(items) + 1):
item, wt, val = items[j-1]
for w in xrange(1, limit + 1):
if wt > w:
table[j][w] = table[j-1][w]
else:
table[j][w] = max(table[j-1][w],
table[j-1][w-wt] + val)
result = []
w = limit
for j in range(len(items), 0, -1):
was_added = table[j][w] != table[j-1][w]
if was_added:
item, wt, val = items[j-1]
result.append(items[j-1])
w -= wt
return result
bagged = knapsack01_dp(items, maxwt) print("Bagged the following %i items\n " % len(bagged) +
'\n '.join('%i off: %s' % (len(list(grp)), item[0])
for item,grp in groupby(sorted(bagged))))
print("for a total value of %i and a total weight of %i" % (
sum(item[2] for item in bagged), sum(item[1] for item in bagged)))</lang>
Non-zero-one solution
<lang Python>items = ( ("map", 9, 150, 1), ("compass", 13, 35, 1), ("water", 153, 200, 3), ("sandwich", 50, 60, 2), ("glucose", 15, 60, 2), ("tin", 68, 45, 3), ("banana", 27, 60, 3), ("apple", 39, 40, 3), ("cheese", 23, 30, 1), ("beer", 52, 10, 3), ("suntan cream",11, 70, 1), ("camera", 32, 30, 1), ("t-shirt", 24, 15, 2), ("trousers", 48, 10, 2), ("umbrella", 73, 40, 1), ("w-trousers", 42, 70, 1), ("w-overcoat", 43, 75, 1), ("note-case", 22, 80, 1), ("sunglasses", 7, 20, 1), ("towel", 18, 12, 2), ("socks", 4, 50, 1), ("book", 30, 10, 2), )
- cache: could just use memoize module, but explicit caching is clearer
def choose_item(weight, idx, cache):
if idx < 0: return 0, []
k = (weight, idx) if k in cache: return cache[k]
name, w, v, qty = items[idx] best_v, best_list = 0, []
for i in range(0, qty + 1):
wlim = weight - i * w
if wlim < 0: break
val, taken = choose_item(wlim, idx - 1, cache)
if val + i * v > best_v:
best_v = val + i * v
best_list = taken[:]
best_list.append(i)
cache[k] = [best_v, best_list] return best_v, best_list
v, lst = choose_item(400, len(items) - 1, {})
w = 0
for i, cnt in enumerate(lst):
if cnt > 0:
print cnt, items[i][0]
w = w + items[i][1] * cnt
print "Total weight:", w, "Value:", v</lang>
REXX
Originally, the combination generator/checker subroutine (SIM) was recursive and made the program solution generic (and very concise). However, a recursive solution also made the solution much more slower, so the combination generator/checker was "unrolled" and converted into discrete combination checks (based on the number of items). The unused combinatorial checks were discarded and only the pertinent code was retained. It made no sense to include all the unused subroutines here as space appears to be a premium for some entries in Rosetta Code. <lang rexx>/*REXX pgm solves a knapsack problem (22 items +repeats, wt. restriction*/ @.= @.1 ='map 9 150' @.2 ='compass 13 35' @.3 ='water 153 200 2' @.4 ='sandwich 50 60 2' @.5 ='glucose 15 60 2' @.6 ='tin 68 45 3' @.7 ='banana 27 60 3' @.8 ='apple 39 40 3' @.9 ='cheese 23 30' @.10='beer 52 10 3' @.11='suntan_cream 11 70' @.12='camera 32 30' @.13='T-shirt 24 15 2' @.14='trousers 48 10 2' @.15='umbrella 73 40' @.16='waterproof_trousers 42 70' @.17='waterproof_overclothes 43 75' @.18='note-case 22 80' @.19='sunglasses 7 20' @.20='towel 18 12 2' @.21='socks 4 50' @.22='book 30 10 2'
maxWeight=400 /*the maximum weight for knapsack*/ say; say 'maximum weight allowed for a knapsack:' comma(maxWeight); say maxL=length('item') /*maximum width for table names. */ maxL=length('knapsack items') /*maximum width for table names. */ maxW=length('weight') /* " " " " weights*/ maxV=length('value') /* " " " " values.*/ maxQ=length('pieces') /* " " " " quant. */ highQ=0 /*max quantity specified (if any)*/ items=0; i.=; w.=0; v.=0; q.=0; Tw=0; Tv=0; Tq=0 /*initialize stuff.*/ /*────────────────────────────────sort the choices by decreasing weight.*/
/*this minimizes # combinations. */
do j=1 while @.j\== /*process each choice and sort. */
_=@.j; _wt=word(_,2) /*choose first item (arbitrary). */
_wt=word(_,2)
do k=j+1 while @.k\== /*find a possible heavier item. */
?wt=word(@.k,2)
if ?wt>_wt then do; _=@.k; @.k=@.j; @.j=_; _wt=?wt; end
end /*k*/
end /*j*/
obj=j-1 /*adjust for the DO loop index. */ /*────────────────────────────────build list of choices.────────────────*/
do j=1 for obj /*build a list of choices. */
_=space(@.j) /*remove superfluous blanks. */
parse var _ item w v q . /*parse original choice for table*/
if w>maxWeight then iterate /*if the weight > maximum, ignore*/
Tw=Tw+w; Tv=Tv+v; Tq=Tq+1 /*add totals up (for alignment). */
maxL=max(maxL,length(item)) /*find maximum width for item. */
if q== then q=1
highQ=max(highQ,q)
items=items+1 /*bump the item counter. */
i.items=item; w.items=w; v.items=v; q.items=q
do k=2 to q; items=items+1 /*bump the item counter. */
i.items=item; w.items=w; v.items=v; q.items=q
Tw=Tw+w; Tv=Tv+v; Tq=Tq+1
end /*k*/
end /*j*/
maxW=max(maxW,length(comma(Tw))) /*find maximum width for weight. */ maxV=max(maxV,length(comma(Tv))) /* " " " " value. */ maxQ=max(maxQ,length(comma(Tq))) /* " " " " quantity*/ maxL=maxL+maxL%4+4 /*extend width of name for table.*/ /*────────────────────────────────show the list of choices.─────────────*/ call hdr 'item'; do j=1 for obj /*show all choices, nice format. */
parse var @.j item weight value q .
if highq==1 then q=
else if q== then q=1
call show item,weight,value,q
end /*j*/
say; say 'number of items:' items; say /*─────────────────────────────────────examine the possible choices. */ h=items; m=maxWeight; $=0; call sim37 /*─────────────────────────────────────show the best choice (weight,val)*/
do h-1; ?=strip(strip(?),"L",0); end
bestC=?; bestW=0; bestV=$; highQ=0; totP=words(bestC) call hdr 'best choice'
do j=1 to totP /*J is modified within DO loop. */
_=word(bestC,j); _w=w._; _v=v._; q=1
if _==0 then iterate
do k=j+1 to totP
__=word(bestC,k); if i._\==i.__ then leave
j=j+1; w._=w._+_w; v._=v._+_v; q=q+1
end /*k*/
call show i._,w._,v._,q; bestW=bestw+w._
end /*j*/
call hdr2; say call show 'best weight' ,bestW /*show a nicely formatted winnerW*/ call show 'best value' ,,bestV /*show a nicely formatted winnerV*/ call show 'knapsack items',,,totP /*show a nicely formatted pieces.*/ exit /*stick a fork in it, we're done.*/ /*────────────────────────────────COMMA subroutine──────────────────────*/ comma: procedure; parse arg _,c,p,t;arg ,cu;c=word(c ",",1)
if cu=='BLANK' then c=' ';o=word(p 3,1);p=abs(o);t=word(t 999999999,1)
if \datatype(p,'W')|\datatype(t,'W')|p==0|arg()>4 then return _;n=_'.9'
#=123456789;k=0;if o<0 then do;b=verify(_,' ');if b==0 then return _
e=length(_)-verify(reverse(_),' ')+1;end;else do;b=verify(n,#,"M")
e=verify(n,#'0',,verify(n,#"0.",'M'))-p-1;end
do j=e to b by -p while k<t;_=insert(c,_,j);k=k+1;end;return _
/*────────────────────────────────HDR subroutine────────────────────────*/ hdr: parse arg _item_,_; if highq\==1 then _=center('pieces',maxq)
call show center( _item_ ,maxL),,
center('weight',maxW),,
center('value' ,maxV),,
center(_ ,maxQ)
call hdr2 return /*────────────────────────────────HDR2 subroutine───────────────────────*/ hdr2: _=maxQ; if highq==1 then _=0; call show copies('=' ,maxL),,
copies('=' ,maxW),,
copies('=' ,maxV),,
copies('=' ,_ )
return /*────────────────────────────────J? subroutine─────────────────────────*/ j?: parse arg _,?; $=value('V'_); do j=1 for _; ?=? value('J'j); end; return /*────────────────────────────────SHOW subroutine───────────────────────*/ show: parse arg _item,_weight,_value,_quant
say translate(left(_item,maxL,'─'),,'_'),
right(comma(_weight),maxW),
right(comma(_value ),maxV),
right(comma(_quant ),maxQ)
return /*─────────────────────────────────────SIM37 subroutine─────────────────*/ sim37:do j1=0 for h+1; w1=w.j1;v1=v.j1;if v1>$ then call j? 1 do j2=j1+(j1\==0) to h if w.j2+w1>m then iterate j1;w2=w1+w.j2;v2=v1+v.j2;if v2>$ then call j? 2 do j3=j2+(j2\==0) to h if w.j3+w2>m then iterate j2;w3=w2+w.j3;v3=v2+v.j3;if v3>$ then call j? 3 do j4=j3+(j3\==0) to h if w.j4+w3>m then iterate j3;w4=w3+w.j4;v4=v3+v.j4;if v4>$ then call j? 4 do j5=j4+(j4\==0) to h if w.j5+w4>m then iterate j4;w5=w4+w.j5;v5=v4+v.j5;if v5>$ then call j? 5 do j6=j5+(j5\==0) to h if w.j6+w5>m then iterate j5;w6=w5+w.j6;v6=v5+v.j6;if v6>$ then call j? 6 do j7=j6+(j6\==0) to h if w.j7+w6>m then iterate j6;w7=w6+w.j7;v7=v6+v.j7;if v7>$ then call j? 7 do j8=j7+(j7\==0) to h if w.j8+w7>m then iterate j7;w8=w7+w.j8;v8=v7+v.j8;if v8>$ then call j? 8 do j9=j8+(j8\==0) to h if w.j9+w8>m then iterate j8;w9=w8+w.j9;v9=v8+v.j9;if v9>$ then call j? 9 do j10=j9+(j9\==0) to h if w.j10+w9>m then iterate j9;w10=w9+w.j10;v10=v9+v.j10;if v10>$ then call j? 10 do j11=j10+(j10\==0) to h if w.j11+w10>m then iterate j10;w11=w10+w.j11;v11=v10+v.j11;if v11>$ then call j? 11 do j12=j11+(j11\==0) to h if w.j12+w11>m then iterate j11;w12=w11+w.j12;v12=v11+v.j12;if v12>$ then call j? 12 do j13=j12+(j12\==0) to h if w.j13+w12>m then iterate j12;w13=w12+w.j13;v13=v12+v.j13;if v13>$ then call j? 13 do j14=j13+(j13\==0) to h if w.j14+w13>m then iterate j13;w14=w13+w.j14;v14=v13+v.j14;if v14>$ then call j? 14 do j15=j14+(j14\==0) to h if w.j15+w14>m then iterate j14;w15=w14+w.j15;v15=v14+v.j15;if v15>$ then call j? 15 do j16=j15+(j15\==0) to h if w.j16+w15>m then iterate j15;w16=w15+w.j16;v16=v15+v.j16;if v16>$ then call j? 16 do j17=j16+(j16\==0) to h if w.j17+w16>m then iterate j16;w17=w16+w.j17;v17=v16+v.j17;if v17>$ then call j? 17 do j18=j17+(j17\==0) to h if w.j18+w17>m then iterate j17;w18=w17+w.j18;v18=v17+v.j18;if v18>$ then call j? 18 do j19=j18+(j18\==0) to h if w.j19+w18>m then iterate j18;w19=w18+w.j19;v19=v18+v.j19;if v19>$ then call j? 19 do j20=j19+(j19\==0) to h if w.j20+w19>m then iterate j19;w20=w19+w.j20;v20=v19+v.j20;if v20>$ then call j? 20 do j21=j20+(j20\==0) to h if w.j21+w20>m then iterate j20;w21=w20+w.j21;v21=v20+v.j21;if v21>$ then call j? 21 do j22=j21+(j21\==0) to h if w.j22+w21>m then iterate j21;w22=w21+w.j22;v22=v21+v.j22;if v22>$ then call j? 22 do j23=j22+(j22\==0) to h if w.j23+w22>m then iterate j22;w23=w22+w.j23;v23=v22+v.j23;if v23>$ then call j? 23 do j24=j23+(j23\==0) to h if w.j24+w23>m then iterate j23;w24=w23+w.j24;v24=v23+v.j24;if v24>$ then call j? 24 do j25=j24+(j24\==0) to h if w.j25+w24>m then iterate j24;w25=w24+w.j25;v25=v24+v.j25;if v25>$ then call j? 25 do j26=j25+(j25\==0) to h if w.j26+w25>m then iterate j25;w26=w25+w.j26;v26=v25+v.j26;if v26>$ then call j? 26 do j27=j26+(j26\==0) to h if w.j27+w26>m then iterate j26;w27=w26+w.j27;v27=v26+v.j27;if v27>$ then call j? 27 do j28=j27+(j27\==0) to h if w.j28+w27>m then iterate j27;w28=w27+w.j28;v28=v27+v.j28;if v28>$ then call j? 28 do j29=j28+(j28\==0) to h if w.j29+w28>m then iterate j28;w29=w28+w.j29;v29=v28+v.j29;if v29>$ then call j? 29 do j30=j29+(j29\==0) to h if w.j30+w29>m then iterate j29;w30=w29+w.j30;v30=v29+v.j30;if v30>$ then call j? 30 do j31=j30+(j30\==0) to h if w.j31+w30>m then iterate j30;w31=w30+w.j31;v31=v30+v.j31;if v31>$ then call j? 31 do j32=j31+(j31\==0) to h if w.j32+w31>m then iterate j31;w32=w31+w.j32;v32=v31+v.j32;if v32>$ then call j? 32 do j33=j32+(j32\==0) to h if w.j33+w32>m then iterate j32;w33=w32+w.j33;v33=v32+v.j33;if v33>$ then call j? 33 do j34=j33+(j33\==0) to h if w.j34+w33>m then iterate j33;w34=w33+w.j34;v34=v33+v.j34;if v34>$ then call j? 34 do j35=j34+(j34\==0) to h if w.j35+w34>m then iterate j34;w35=w34+w.j35;v35=v34+v.j35;if v35>$ then call j? 35 do j36=j35+(j35\==0) to h if w.j36+w35>m then iterate j35;w36=w35+w.j36;v36=v35+v.j36;if v36>$ then call j? 36 do j37=j36+(j36\==0) to h if w.j37+w36>m then iterate j36;w37=w36+w.j37;v37=v36+v.j37;if v37>$ then call j? 37 end;end;end;end;end;end;end;end;end;end;end;end;end;end;end;end;end;end;end;end;end;end;end;end;end;end;end;end;end;end;end;end;end;end;end;end;end return</lang>
- Output:
maximum weight allowed for a knapsack: 400
item weight value pieces
=============================== ====== ===== ======
water────────────────────────── 153 200 2
umbrella─────────────────────── 73 40 1
tin──────────────────────────── 68 45 3
beer─────────────────────────── 52 10 3
sandwich─────────────────────── 50 60 2
trousers─────────────────────── 48 10 2
waterproof overclothes───────── 43 75 1
waterproof trousers──────────── 42 70 1
apple────────────────────────── 39 40 3
camera───────────────────────── 32 30 1
book─────────────────────────── 30 10 2
banana───────────────────────── 27 60 3
T-shirt──────────────────────── 24 15 2
cheese───────────────────────── 23 30 1
note-case────────────────────── 22 80 1
towel────────────────────────── 18 12 2
glucose──────────────────────── 15 60 2
compass──────────────────────── 13 35 1
suntan cream─────────────────── 11 70 1
map──────────────────────────── 9 150 1
sunglasses───────────────────── 7 20 1
socks────────────────────────── 4 50 1
number of items: 37
best choice weight value pieces
=============================== ====== ===== ======
water────────────────────────── 153 200 1
waterproof overclothes───────── 43 75 1
banana───────────────────────── 81 180 3
cheese───────────────────────── 23 30 1
note-case────────────────────── 22 80 1
glucose──────────────────────── 30 120 2
compass──────────────────────── 13 35 1
suntan cream─────────────────── 11 70 1
map──────────────────────────── 9 150 1
sunglasses───────────────────── 7 20 1
socks────────────────────────── 4 50 1
=============================== ====== ===== ======
best weight──────────────────── 396
best value───────────────────── 1,010
knapsack items───────────────── 14
Tcl
Classic dumb search algorithm: <lang tcl># The list of items to consider, as list of lists set items {
{map 9 150 1}
{compass 13 35 1}
{water 153 200 2}
{sandwich 50 60 2}
{glucose 15 60 2}
{tin 68 45 3}
{banana 27 60 3}
{apple 39 40 3}
{cheese 23 30 1}
{beer 52 10 3}
{{suntan cream} 11 70 1}
{camera 32 30 1}
{t-shirt 24 15 2}
{trousers 48 10 2}
{umbrella 73 40 1}
{{waterproof trousers} 42 70 1}
{{waterproof overclothes} 43 75 1}
{note-case 22 80 1}
{sunglasses 7 20 1}
{towel 18 12 2}
{socks 4 50 1}
{book 30 10 2}
}
- Simple extraction functions
proc countednames {chosen} {
set names {}
foreach item $chosen {
lappend names [lindex $item 3] [lindex $item 0]
} return $names
} proc weight {chosen} {
set weight 0
foreach item $chosen {
incr weight [expr {[lindex $item 3] * [lindex $item 1]}]
} return $weight
} proc value {chosen} {
set value 0
foreach item $chosen {
incr value [expr {[lindex $item 3] * [lindex $item 2]}]
} return $value
}
- Recursive function for searching over all possible choices of items
proc knapsackSearch {items {chosen {}}} {
# If we've gone over the weight limit, stop now
if {[weight $chosen] > 400} {
return
}
# If we've considered all of the items (i.e., leaf in search tree)
# then see if we've got a new best choice.
if {[llength $items] == 0} {
global best max set v [value $chosen] if {$v > $max} { set max $v set best $chosen } return
}
# Branch, so recurse for chosing the current item or not
set this [lindex $items 0]
set rest [lrange $items 1 end]
knapsackSearch $rest $chosen
for {set i 1} {$i<=[lindex $this 3]} {incr i} {
knapsackSearch $rest \ [concat $chosen [list [lreplace $this end end $i]]]
}
}
- Initialize a few global variables
set best {} set max 0
- Do the brute-force search
knapsackSearch $items
- Pretty-print the results
puts "Best filling has weight of [expr {[weight $best]/100.0}]kg and score [value $best]" puts "Best items:" foreach {count item} [countednames $best] {
puts "\t$count * $item"
}</lang>
- Output:
Best filling has weight of 3.96kg and score 1010 Best items: 1 * map 1 * compass 1 * water 2 * glucose 3 * banana 1 * cheese 1 * suntan cream 1 * waterproof overclothes 1 * note-case 1 * sunglasses 1 * socks
Ursala
Instead of an ad-hoc solution, we can convert this task to a mixed integer programming problem instance and solve it with the lpsolve library, which is callable in Ursala. <lang Ursala>#import std
- import flo
- import lin
items = # name: (weight,value,limit)
<
'map': (9,150,1), 'compass': (13,35,1), 'water': (153,200,3), 'sandwich': (50,60,2), 'glucose': (15,60,2), 'tin': (68,45,3), 'banana': (27,60,3), 'apple': (39,40,3), 'cheese': (23,30,1), 'beer': (52,10,3), 'suntan cream': (11,70,1), 'camera': (32,30,1), 't-shirt': (24,15,2), 'trousers': (48,10,2), 'umbrella': (73,40,1), 'waterproof trousers': (42,70,1), 'waterproof overclothes': (43,75,1), 'note-case': (22,80,1), 'sunglasses': (7,20,1), 'towel': (18,12,2), 'socks': (4,50,1), 'book': (30,10,2)>
system = # convert the item list to mixed integer programming problem specification
linear_system$[
integers: ~&nS, upper_bounds: * ^|/~& float@rr, lower_bounds: @nS ~&\*0.+ :/'(slack)', costs: * ^|/~& negative+ float@rl, equations: ~&iNC\400.+ :/(1.,'(slack)')+ * ^|rlX/~& float@l]
format = @t --^*p\pad` @nS @mS printf/*'%0.0f '
- show+
main = format solution system items</lang>
The linear_system$[...] function takes the item list as an argument and returns a data structure with the following fields, which is passed to the solution function, which calls the lpsolve routines.
integersdeclares that all variables in the list take integer valuesupper_boundsassociates an upper bound for each variable directly as givenlower_boundsare zero for all variables in the table, and for an additional slack variable, which is not required to be an integer and won't appear in the solutioncostsare also taken from the table and negated because their value is to be maximized rather than minimized as in the standard formulationequationsspecifies the single constraint that the total weights of the selected items in the selected quantities plus the slack equal 400
The format function converts the output list to a readable form.
- Output:
3 banana 1 cheese 1 compass 2 glucose 1 map 1 note-case 1 socks 1 sunglasses 1 suntan cream 1 water 1 waterproof overclothes