# Knapsack problem/0-1

(Redirected from 0-1 knapsack problem)
Knapsack problem/0-1
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 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 trip.

Here is the list:

Table of potential knapsack items
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 or diminish the items, so he can only take whole units of any item.

Show which items the tourist can carry in his knapsack so that their total weight does not exceed 400 dag [4 kg],   and their total value is maximized.

[dag = decagram = 10 grams]

## 11l

Translation of: Python
F totalvalue(comb)
V totwt = 0
V totval = 0
L(item, wt, val) comb
totwt += wt
totval += val
R I totwt <= 400 {(totval, -totwt)} E (0, 0)

V items = [
(‘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)
]

F knapsack01_dp(items, limit)
V table = [[0] * (limit + 1)] * (items.len + 1)

L(j) 1 .. items.len
V (item, wt, val) = items[j - 1]
L(w) 1 .. limit
I wt > w
table[j][w] = table[j - 1][w]
E
table[j][w] = max(table[j - 1][w], table[j - 1][w - wt] + val)

[(String, Int, Int)] result
V w = limit
L(j) (items.len .< 0).step(-1)
I table[j][w] != table[j - 1][w]
V (item, wt, val) = items[j - 1]
result.append(items[j - 1])
w -= wt
R result

V bagged = knapsack01_dp(items, 400)
print("Bagged the following items\n  "sorted(bagged.map((item, _, _2) -> item)).join("\n  "))
V (val, wt) = totalvalue(bagged)
print(‘for a total value of #. and a total weight of #.’.format(val, -wt))
Output:
Bagged the following items
banana
compass
glucose
map
note-case
sandwich
socks
sunglasses
suntan cream
water
waterproof overclothes
waterproof trousers
for a total value of 1030 and a total weight of 396

## 360 Assembly

Non recurvive brute force version.

*      Knapsack problem/0-1      16/02/2017
KNAPSA01 CSECT
USING  KNAPSA01,R13
B      72(R15)
DC     17F'0'
STM    R14,R12,12(R13)
ST     R13,4(R15)
ST     R15,8(R13)
LR     R13,R15            end of prolog
L      R0,N               n
LA     R1,1
POWER  MH     R1,=H'2'           *2
BCT    R0,POWER
BCTR   R1,0               -1
ST     R1,IMAX            imax=2**n-1
SR     R6,R6              i=0
DO WHILE=(C,R6,LE,IMAX)   do i=0 to imax
SR     R10,R10            im=0
SR     R8,R8              iw=0
SR     R9,R9              iv=0
LA     R7,1               j=1
DO WHILE=(C,R7,LE,N)      do j=1 to n
LR     R1,R6              i
LR     R2,R7              j
BAL    R14,TSTBIT         call tstbit(i,j)
IF C,R0,EQ,=F'1' THEN     if tstbit(i,j)=1 then
LA     R10,1(R10)         im=im+1
LR     R3,R7              j
BCTR   R3,0
SLA    R3,5
LA     R1,24(R3)
A      R8,DATA(R1)        iw=iw+data(j).w
LA     R1,28(R3)
A      R9,DATA(R1)        iv=iv+data(j).v
ENDIF  ,                  endif
LA     R7,1(R7)           j=j+1
ENDDO  ,                  enddo j
IF C,R8,LE,MAXW,AND,C,R9,GT,XV THEN  if w<=maxw and iv>xv then
ST     R6,XB              xb=i
ST     R10,XM             xm=im
ST     R8,XW              xw=iw
ST     R9,XV              xv=iv
ENDIF  ,                  endif
LA     R6,1(R6)           i=i+1
ENDDO  ,                  enddo i
MVC    PG(2),=C'n='
L      R1,N               n
XDECO  R1,XDEC            edit n
MVC    PG+2(2),XDEC+10
XPRNT  PG,L'PG            print buffer
LA     R6,1
DO WHILE=(C,R6,LE,N)      do i=1 to n
L      R1,XB              xb
LR     R2,R6              i
BAL    R14,TSTBIT         call tstbit(xb,i)
IF C,R0,EQ,=F'1' THEN     if tstbit(xb,i)=1 then
LR     R1,R6              i
BCTR   R1,0
SLA    R1,5
LA     R2,DATA(R1)        @data(i).n
MVC    PG(24),0(R2)
XPRNT  PG,24              print item
ENDIF  ,                  endif
LA     R6,1(R6)           i=i+1
ENDDO  ,                  enddo i
L      R1,XM              xm
XDECO  R1,XDEC            edit xm
MVC    PGT+6(2),XDEC+10
L      R1,XW              xw
XDECO  R1,XDEC            edit xw
MVC    PGT+16(3),XDEC+9
L      R1,XV              xv
XDECO  R1,XDEC            edit xv
MVC    PGT+26(4),XDEC+8
XPRNT  PGT,L'PGT          print buffer
L      R13,4(0,R13)       epilog
LM     R14,R12,12(R13)
XR     R15,R15
BR     R14                exit
TSTBIT EQU    *                  R1 value to test the R2 bit
LA     R3,32              32
SR     R3,R2              (32-i)
STC    R3,XSLL+3
LR     R0,R1              n
EX     0,XSLL             SLL R0,(32-i)
SRL    R0,31
BR     R14                return R0
XSLL   SLL    R0,0               shift left logical
*
MAXW   DC     F'400'             maximum weight
N      DC     A((DATAE-DATA)/32)
IMAX   DS     F                  number of combinations
XB     DS     F                  max vector
XM     DS     F                  max items
XW     DS     F                  max weight
XV     DS     F                  max value
PG     DC     CL80' '
PGT    DC     CL32'items=.. weight=... value=....'
XDEC   DS     CL12
DATA   DC     CL24'map',F'9',F'150'
DC     CL24'compass',F'13',F'35'
DC     CL24'water',F'153',F'200'
DC     CL24'sandwich',F'50',F'160'
DC     CL24'glucose',F'15',F'60'
DC     CL24'tin',F'68',F'45'
DC     CL24'banana',F'27',F'60'
DC     CL24'apple',F'39',F'40'
DC     CL24'cheese',F'23',F'30'
DC     CL24'beer',F'52',F'10'
DC     CL24'suntan cream',F'11',F'70'
DC     CL24'camera',F'32',F'30'
DC     CL24'T-shirt',F'24',F'15'
DC     CL24'trousers',F'48',F'10'
DC     CL24'umbrella',F'73',F'40'
DC     CL24'book',F'30',F'10'
DC     CL24'waterproof trousers',F'42',F'70'
DC     CL24'waterproof overclothes',F'43',F'75'
DC     CL24'note-case',F'22',F'80'
DC     CL24'sunglasses',F'7',F'20'
DC     CL24'towel',F'18',F'12'
DC     CL24'socks',F'4',F'50'
DATAE  DC     0C
YREGS
END    KNAPSA01
Output:
n=22
map
compass
water
sandwich
glucose
banana
suntan cream
waterproof trousers
waterproof overclothes
note-case
sunglasses
socks
items=12 weight=396 value=1030

procedure Knapsack_01 is

type Item is record
Name   : US.Unbounded_String;
Weight : Positive;
Value  : Positive;
Taken  : Boolean;
end record;

type Item_Array is array (Positive range <>) of Item;

function Total_Weight (Items : Item_Array; Untaken : Boolean := False) return Natural is
Sum : Natural := 0;
begin
for I in Items'Range loop
if Untaken or else Items (I).Taken then
Sum := Sum + Items (I).Weight;
end if;
end loop;
return Sum;
end Total_Weight;

function Total_Value (Items : Item_Array; Untaken : Boolean := False) return Natural is
Sum : Natural := 0;
begin
for I in Items'Range loop
if Untaken or else Items (I).Taken then
Sum := Sum + Items (I).Value;
end if;
end loop;
return Sum;
end Total_Value;

function Max (Left, Right : Natural) return Natural is
begin
if Right > Left then
return Right;
else
return Left;
end if;
end Max;

procedure Solve_Knapsack_01 (Items : in out Item_Array;
Weight_Limit : Positive := 400) is
type W_Array is array (0..Items'Length, 0..Weight_Limit) of Natural;
W : W_Array := (others => (others => 0));
begin
-- fill W
for I in Items'Range loop
for J in 1 .. Weight_Limit loop
if Items (I).Weight > J then
W (I, J) := W (I - 1, J);
else
W (I, J) := Max (W (I - 1, J),
W (I - 1, J - Items (I).Weight) + Items (I).Value);
end if;
end loop;
end loop;
declare
Rest : Natural := Weight_Limit;
begin
for I in reverse Items'Range loop
if W (I, Rest) /= W (I - 1, Rest) then
Items (I).Taken := True;
Rest := Rest - Items (I).Weight;
end if;
end loop;
end;
end Solve_Knapsack_01;

All_Items : Item_Array :=
( (US.To_Unbounded_String ("map"),                      9, 150, False),
(US.To_Unbounded_String ("compass"),                 13,  35, False),
(US.To_Unbounded_String ("water"),                  153, 200, False),
(US.To_Unbounded_String ("sandwich"),                50, 160, False),
(US.To_Unbounded_String ("glucose"),                 15,  60, False),
(US.To_Unbounded_String ("tin"),                     68,  45, False),
(US.To_Unbounded_String ("banana"),                  27,  60, False),
(US.To_Unbounded_String ("apple"),                   39,  40, False),
(US.To_Unbounded_String ("cheese"),                  23,  30, False),
(US.To_Unbounded_String ("beer"),                    52,  10, False),
(US.To_Unbounded_String ("suntan cream"),            11,  70, False),
(US.To_Unbounded_String ("camera"),                  32,  30, False),
(US.To_Unbounded_String ("t-shirt"),                 24,  15, False),
(US.To_Unbounded_String ("trousers"),                48,  10, False),
(US.To_Unbounded_String ("umbrella"),                73,  40, False),
(US.To_Unbounded_String ("waterproof trousers"),     42,  70, False),
(US.To_Unbounded_String ("waterproof overclothes"),  43,  75, False),
(US.To_Unbounded_String ("note-case"),               22,  80, False),
(US.To_Unbounded_String ("sunglasses"),               7,  20, False),
(US.To_Unbounded_String ("towel"),                   18,  12, False),
(US.To_Unbounded_String ("socks"),                    4,  50, False),
(US.To_Unbounded_String ("book"),                    30,  10, False) );

begin
Solve_Knapsack_01 (All_Items, 400);
Ada.Text_IO.Put_Line ("Total Weight: " & Natural'Image (Total_Weight (All_Items)));
Ada.Text_IO.Put_Line ("Total Value:  " & Natural'Image (Total_Value  (All_Items)));
for I in All_Items'Range loop
if All_Items (I).Taken then
Ada.Text_IO.Put_Line ("   " & US.To_String (All_Items (I).Name));
end if;
end loop;
end Knapsack_01;
Output:
Total Weight:  396
Total Value:   1030
Items:
map
compass
water
sandwich
glucose
banana
suntan cream
waterproof trousers
waterproof overclothes
note-case
sunglasses
socks

## APL

retNapSack;sum;b;list;total
[1]   total400
[2]   list("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)
[3]   listlist[3¨list]
[4]
[5]   ret
[6]   :while 0≠⍴list
[7]       retret,(btotal>sum+\2¨list)/list
[8]       list1(~b)/list
[9]       totaltotal-sum¯1(total>sum)/sum
[10]  :end
[11]  retret,⊂'TOTALS:' (+/2¨ret)(+/3¨ret)

Output:
NapSack
water                  153  200
sandwich                50  160
map                      9  150
note-case               22   80
waterproof overclothes  43   75
suntan cream            11   70
waterproof trousers     42   70
glucose                 15   60
banana                  27   60
socks                    4   50
compass                 13   35
sunglasses               7   20
TOTALS:                396 1030

Average runtime: 0.000168 seconds

## AWK

# syntax: GAWK -f KNAPSACK_PROBLEM_0-1.AWK
BEGIN {
#   arr["item,weight"] = value
arr["map,9"] = 150
arr["compass,13"] = 35
arr["water,153"] = 200
arr["sandwich,50"] = 160
arr["glucose,15"] = 60
arr["tin,68"] = 45
arr["banana,27"] = 60
arr["apple,39"] = 40
arr["cheese,23"] = 30
arr["beer,52"] = 10
arr["suntan cream,11"] = 70
arr["camera,32"] = 30
arr["T-shirt,24"] = 15
arr["trousers,48"] = 10
arr["umbrella,73"] = 40
arr["waterproof trousers,42"] = 70
arr["waterproof overclothes,43"] = 75
arr["note-case,22"] = 80
arr["sunglasses,7"] = 20
arr["towel,18"] = 12
arr["socks,4"] = 50
arr["book,30"] = 10
sack_size = 400 # dag
PROCINFO["sorted_in"] = "@val_num_desc"
for (i in arr) {
if (total_weight >= sack_size) {
break
}
split(i,tmp,",")
weight = tmp[2]
if (total_weight + weight <= sack_size) {
printf("%s\n",tmp[1])
total_items++
total_value += arr[i]
total_weight += weight
}
}
printf("items=%d (out of %d) weight=%d value=%d\n",total_items,length(arr),total_weight,total_value)
exit(0)
}
Output:
water
sandwich
map
note-case
waterproof overclothes
waterproof trousers
suntan cream
banana
glucose
socks
compass
sunglasses
items=12 (out of 22) weight=396 value=1030

## BASIC

### QBasic

Works with: QBasic version 1.1
Works with: QuickBasic version 4.5
Translation of: QB64
N = 7: G = 5: a = 2 ^ (N + 1) ' Author: DANILIN & Editor: Jjuanhdez or Unknow
RANDOMIZE TIMER
DIM L(N), C(N), j(N), q(a), d(a), q\$(a)

FOR i = a - 1 TO (a - 1) \ 2 STEP -1
k = i
DO  ' cipher 0-1
q\$(i) = LTRIM\$(STR\$(k MOD 2)) + q\$(i)
k = INT(k / 2)
LOOP UNTIL k = 0
q\$(i) = MID\$(q\$(i), 2, LEN(q\$(i)))
NEXT i

PRINT " #            Mass          Cost"
FOR i = 1 TO N
L(i) = INT(RND * 3 + 1)' mass & cost
C(i) = 10 + INT(RND * 9)
PRINT i, L(i), C(i)
NEXT i  ' origin

PRINT CHR\$(10) + "Mass          Cost           Chifer"
FOR h = a - 1 TO (a - 1) / 2 STEP -1
FOR k = 1 TO N
j(k) = VAL(MID\$(q\$(h), k, 1))    ' j() = cipher
q(h) = q(h) + L(k) * j(k) * C(k) ' 0 or 1
d(h) = d(h) + L(k) * j(k)
NEXT k
IF d(h) <= G THEN PRINT d(h), q(h), q\$(h)
NEXT h

PRINT CHR\$(10) + "Mass          MAX            Chifer"
max = 0: h = 1
FOR i = 1 TO a
IF d(i) <= G AND q(i) > max THEN max = q(i): h = i
NEXT i
PRINT d(h), q(h), q\$(h)
Output:
Same as QB64 entry.

### Yabasic

Translation of: QB64
N = 7 : G = 5 : a = 2^(N+1) ' Author: DANILIN & Editor: Jjuanhdez or Unknow
dim L(N), C(N), j(N), q(a), d(a), q\$(a)

for i = a-1 to int((a-1)/2) step -1
k = i
repeat    // cipher 0-1
q\$(i) = ltrim\$(str\$(mod(k, 2))) + q\$(i)
k = int(k / 2)
until k = 0
q\$(i) = mid\$(q\$(i), 2, len(q\$(i)))
next i

print " #     Mass    Cost"
for i = 1 to N
L(i) = int(ran(3)) + 1    // mass & cost
C(i) = 10 + int(ran(9))
print i, chr\$(9), L(i), chr\$(9), C(i)
next i  // origin

print chr\$(10) + "Mass   Cost      Chifer"
for h = a-1 to (a-1)/2 step -1
for k = 1 to N
j(k) = val(mid\$(q\$(h), k, 1))     // j() = cipher
q(h) = q(h) + L(k) * j(k) * C(k)  // 0 or 1
d(h) = d(h) + L(k) * j(k)
next k
if d(h) <= G  print d(h), chr\$(9), q(h), chr\$(9), q\$(h)
next h

print chr\$(10) + "Mass   MAX       Chifer"
maxx = 0 : h = 1
for i = 1 to a
if d(i) <= G and q(i) > maxx  maxx = q(i) : h = i
next i
print d(h), chr\$(9), q(h), chr\$(9), q\$(h)
end
Output:
Same as QB64 entry
https://jdoodle.com/iembed/v0/suj

## Batch File

:: Initiate command line environment
@echo off
setlocal enabledelayedexpansion

:: Establish arrays we'll be using
set items=map compass water sandwich glucose tin banana apple cheese beer suntancream camera tshirt trousers umbrella waterprooftrousers waterproofoverclothes notecase sunglasses towel socks book
set weight=9 13 153 50 15 68 27 39 23 52 11 32 24 48 73 42 43 22 7 18 4 30
set importance=150 35 200 160 60 45 60 40 30 10 70 30 15 10 40 70 75 80 20 12 50 10

:: Put the above 3 arrays into their own variables with the form of "item[]", "w[]" and "i[]"
set tempnum=0
for %%i in (%items%) do (
set /a tempnum+=1
set item!tempnum!=%%i
)
set tempnum=0
for %%i in (%weight%) do (
set /a tempnum+=1
set w!tempnum!=%%i
)
set tempnum=0
for %%i in (%importance%) do (
set /a tempnum+=1
set i!tempnum!=%%i
)
:: Define the array "r[]" as the ratio between the importance ("i[]") and the weight ("w[]").
for /l %%i in (1,1,22) do set /a r%%i=!i%%i!*100/!w%%i! & rem batch doesn't support decimals, so the numerator is multiplied by 100 to get past this

set totalimportance=0
set totalweight=0
set amount=0

:: Find the largest number in "r[]" and define some temp variables based off it
set tempr=0
set tempitem=0
for /l %%i in (1,1,22) do (
if !r%%i! gtr !tempr! (
set tempr=!r%%i!
set tempitem=%%i
set /a testweight=%totalweight%+!w%%i!
if !tempr!==0 goto end
if !testweight! geq 400 goto end
)
)

:: Do basic error checking using the temp variables from above and either output and end the program or send back to load
set /a totaltempweight=%totalweight%+!w%tempitem%!

if %totaltempweight% gtr 400 (
set !r%tempitem%!=0
)

set totalweight=%totaltempweight%
set /a totalimportance+=!i%tempitem%!
set taken=%taken% !item%tempitem%!
set /a amount+=1
set r%tempitem%=0 & rem set the ratio variable of the item we just added to the knapsack as 0 to stop it repeat

:end
echo List of things taken [%amount%]: %taken%
echo Total Value: %totalimportance%  Total Weight: %totalweight%
pause>nul
Output:
List of things taken [12]:  map socks suntancream glucose notecase sandwich sunglasses compass banana waterproofoverclothes waterprooftrousers water
Total Value: 1030  Total Weight: 396

## BBC BASIC

HIMEM = PAGE + 8000000
nItems% = 22
maxWeight% = 400

DIM Tag{ivalue%, list%(nItems%-1), lp%}
DIM items{(nItems%-1)name\$, weight%, ivalue%}
FOR item% = 0 TO nItems%-1
NEXT

DATA "map", 9, 150, "compass", 13, 35, "water", 153, 200, "sandwich", 50, 160
DATA "glucose", 15, 60, "tin", 68, 45, "banana", 27, 60, "apple", 39, 40
DATA "cheese", 23, 30, "beer", 52, 10, "suntan cream", 11, 70, "camera", 32, 30
DATA "t-shirt", 24, 15, "trousers", 48, 10, "umbrella", 73, 40, "book", 30, 10
DATA "waterproof trousers", 42, 70, "waterproof overclothes", 43, 75
DATA "note-case", 22, 80, "sunglasses", 7, 20, "towel", 18, 12, "socks", 4, 50

carry% = FN_Knapsack(items{()}, nItems% - 1, maxWeight%, cache{()})
FOR i% = 0 TO cache{(carry%)}.lp%-1
n% = cache{(carry%)}.list%(i%)
TotalWeight% += items{(n%)}.weight%
TotalValue% += items{(n%)}.ivalue%
PRINT items{(n%)}.name\$ " "
NEXT
PRINT '"Total weight = " ; TotalWeight%
PRINT "Total value  = " ; TotalValue%
END

DEF FN_Knapsack(i{()}, i%, w%, RETURN m{()})
LOCAL included{}, excluded{}, tmp%, index%
DIM m{(16384)} = Tag{}, included{} = Tag{}, excluded{} = Tag{}

index% = i% << 9 OR w%
IF m{(index%)}.ivalue% THEN = index%

IF i% = 0 THEN
IF i{(0)}.weight% > w% THEN
m{(index%)}.ivalue% = 0 : REM Item doesn't fit
ELSE
m{(index%)}.ivalue% = i{(0)}.ivalue%
m{(index%)}.list%(m{(index%)}.lp%) = 0
m{(index%)}.lp% += 1
ENDIF
= index%
ENDIF

tmp% = FN_Knapsack(i{()}, i% - 1, w%, m{()})
excluded{} = m{(tmp%)}
IF i{(i%)}.weight% > w% THEN
m{(index%)} = excluded{} : REM Item weighs too much
= index%
ELSE
tmp% = FN_Knapsack(i{()}, i% - 1, w% - i{(i%)}.weight%, m{()})
included{} = m{(tmp%)}
included.ivalue% += i{(i%)}.ivalue%
included.list%(included.lp%) = i%
included.lp% += 1
ENDIF

IF included.ivalue% > excluded.ivalue% THEN
m{(index%)} = included{}
ELSE
m{(index%)} = excluded{}
ENDIF
= index%
Output:
map
compass
water
sandwich
glucose
banana
suntan cream
waterproof trousers
waterproof overclothes
note-case
sunglasses
socks

Total weight = 396
Total value  = 1030

## Bracmat

(knapsack=
( things
=   (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)
)
& 0:?maxvalue
& :?sack
=     cumwght
cumvalue
cumsack
name
wght
val
tings
n
ncumwght
ncumvalue
.     !arg
: (?cumwght.?cumvalue.?cumsack.(?name.?wght.?val) ?tings)
& -1:?n
&   whl
' ( 1+!n:~>1:?n
& !cumwght+!n*!wght:~>400:?ncumwght
& !cumvalue+!n*!val:?ncumvalue
& (   !tings:
& (   !ncumvalue:>!maxvalue:?maxvalue
&     !cumsack
(!n:0&|!name)
: ?sack
|
)
\$ ( !ncumwght
. !ncumvalue
.   !cumsack
(!n:0&|!name)
. !tings
)
)
)
)
& out\$(!maxvalue.!sack));

!knapsack;
Output:
1030
.   map
compass
water
sandwich
glucose
banana
suntan cream
waterproof trousers
waterproof overclothes
note-case
sunglasses
socks

## C

#include <stdio.h>
#include <stdlib.h>

typedef struct {
char *name;
int weight;
int value;
} item_t;

item_t items[] = {
{"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},
};

int *knapsack (item_t *items, int n, int w) {
int i, j, a, b, *mm, **m, *s;
mm = calloc((n + 1) * (w + 1), sizeof (int));
m = malloc((n + 1) * sizeof (int *));
m[0] = mm;
for (i = 1; i <= n; i++) {
m[i] = &mm[i * (w + 1)];
for (j = 0; j <= w; j++) {
if (items[i - 1].weight > j) {
m[i][j] = m[i - 1][j];
}
else {
a = m[i - 1][j];
b = m[i - 1][j - items[i - 1].weight] + items[i - 1].value;
m[i][j] = a > b ? a : b;
}
}
}
s = calloc(n, sizeof (int));
for (i = n, j = w; i > 0; i--) {
if (m[i][j] > m[i - 1][j]) {
s[i - 1] = 1;
j -= items[i - 1].weight;
}
}
free(mm);
free(m);
return s;
}

int main () {
int i, n, tw = 0, tv = 0, *s;
n = sizeof (items) / sizeof (item_t);
s = knapsack(items, n, 400);
for (i = 0; i < n; i++) {
if (s[i]) {
printf("%-22s %5d %5d\n", items[i].name, items[i].weight, items[i].value);
tw += items[i].weight;
tv += items[i].value;
}
}
printf("%-22s %5d %5d\n", "totals:", tw, tv);
return 0;
}
Output:
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
totals:                  396  1030

## C#

Library: System
using System;
using System.Collections.Generic;

namespace Tests_With_Framework_4
{

class Bag : IEnumerable<Bag.Item>
{
List<Item> items;
const int MaxWeightAllowed = 400;

public Bag()
{
items = new List<Item>();
}

{
if ((TotalWeight + i.Weight) <= MaxWeightAllowed)
}

public void Calculate(List<Item> items)
{
foreach (Item i in Sorte(items))
{
}
}

List<Item> Sorte(List<Item> inputItems)
{
List<Item> choosenItems = new List<Item>();
for (int i = 0; i < inputItems.Count; i++)
{
int j = -1;
if (i == 0)
{
}
if (i > 0)
{
if (!RecursiveF(inputItems, choosenItems, i, choosenItems.Count - 1, false, ref j))
{
}
}
}
return choosenItems;
}

bool RecursiveF(List<Item> knapsackItems, List<Item> choosenItems, int i, int lastBound, bool dec, ref int indxToAdd)
{
if (!(lastBound < 0))
{
if ( knapsackItems[i].ResultWV < choosenItems[lastBound].ResultWV )
{
}
return RecursiveF(knapsackItems, choosenItems, i, lastBound - 1, true, ref indxToAdd);
}
{
return true;
}
return false;
}

#region IEnumerable<Item> Members
IEnumerator<Item> IEnumerable<Item>.GetEnumerator()
{
foreach (Item i in items)
yield return i;
}
#endregion

#region IEnumerable Members
System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
{
return items.GetEnumerator();
}
#endregion

public int TotalWeight
{
get
{
var sum = 0;
foreach (Item i in this)
{
sum += i.Weight;
}
return sum;
}
}

public class Item
{
public string Name { get; set; } public int Weight { get; set; } public int Value { get; set; } public int ResultWV { get { return  Weight-Value; } }
public override string ToString()
{
return "Name : " + Name + "        Wieght : " + Weight + "       Value : " + Value + "     ResultWV : " + ResultWV;
}
}
}

class Program
{
static void Main(string[] args)
{List<Bag.Item> knapsackItems = new List<Bag.Item>();
knapsackItems.Add(new Bag.Item() { Name = "Map", Weight = 9, Value = 150 });
knapsackItems.Add(new Bag.Item() { Name = "Water", Weight = 153, Value = 200 });
knapsackItems.Add(new Bag.Item() { Name = "Compass", Weight = 13, Value = 35 });
knapsackItems.Add(new Bag.Item() { Name = "Sandwitch", Weight = 50, Value = 160 });
knapsackItems.Add(new Bag.Item() { Name = "Glucose", Weight = 15, Value = 60 });
knapsackItems.Add(new Bag.Item() { Name = "Tin", Weight = 68, Value = 45 });
knapsackItems.Add(new Bag.Item() { Name = "Banana", Weight = 27, Value = 60 });
knapsackItems.Add(new Bag.Item() { Name = "Apple", Weight = 39, Value = 40 });
knapsackItems.Add(new Bag.Item() { Name = "Cheese", Weight = 23, Value = 30 });
knapsackItems.Add(new Bag.Item() { Name = "Beer", Weight = 52, Value = 10 });
knapsackItems.Add(new Bag.Item() { Name = "Suntan Cream", Weight = 11, Value = 70 });
knapsackItems.Add(new Bag.Item() { Name = "Camera", Weight = 32, Value = 30 });
knapsackItems.Add(new Bag.Item() { Name = "T-shirt", Weight = 24, Value = 15 });
knapsackItems.Add(new Bag.Item() { Name = "Trousers", Weight = 48, Value = 10 });
knapsackItems.Add(new Bag.Item() { Name = "Umbrella", Weight = 73, Value = 40 });
knapsackItems.Add(new Bag.Item() { Name = "WaterProof Trousers", Weight = 42, Value = 70 });
knapsackItems.Add(new Bag.Item() { Name = "Note-Case", Weight = 22, Value = 80 });
knapsackItems.Add(new Bag.Item() { Name = "Sunglasses", Weight = 7, Value = 20 });
knapsackItems.Add(new Bag.Item() { Name = "Towel", Weight = 18, Value = 12 });
knapsackItems.Add(new Bag.Item() { Name = "Socks", Weight = 4, Value = 50 });
knapsackItems.Add(new Bag.Item() { Name = "Book", Weight = 30, Value = 10 });
knapsackItems.Add(new Bag.Item() { Name = "waterproof overclothes ", Weight = 43, Value = 75 });

Bag b = new Bag();
b.Calculate(knapsackItems);
b.All(x => { Console.WriteLine(x); return true; });
Console.WriteLine(b.Sum(x => x.Weight));
}
}
}

("Bag" might not be the best name for the class, since "bag" is sometimes also used to refer to a multiset data structure.)

### C#, Alternative Version

C# Knapsak 0-1 Russian Binary ciphers

Russian Knapsack 0-1 synthesizes all ciphers from 0 & 1 adding left +1 register and 0 remain on left in cipher

Number of comparisons decreases from N! to 2^N for example N=8 N!=40320 >> 2^N=256

Random values origin are automatically assigned create integral of quantity and quality

using System;		// Knapsack C# binary DANILIN
using System.Text;	// rextester.com/YRFA61366
namespace Knapsack
{
class Knapsack
{
static void Main()
{
int n = 7;
int Inside = 5;
int all=Convert.ToInt32(Math.Pow(2,(n+1)));
int[] mass = new int[n];
int[] cost = new int[n];
int[] jack = new int[n];
int[] quality = new int[all];
int[] amount = new int[all];
int i; 			// circle
int k; 			// circle
int dec;
string[] bin = new string[all];
int list;
int max;
int max_num;
Random rand = new Random();

for (i=0; i<n; i++)
{
mass[i]=1+rand.Next(3);
cost[i]=10+rand.Next(9);
Console.WriteLine("{0} {1} {2}", i+1, mass[i], cost[i]);
}
Console.WriteLine();

for (list = all-1; list>(all-1)/2; list--)
{
dec=list;
while (dec > 0)
{
bin[list] = dec % 2 + bin[list]; // from 10 to 2
dec/=2;
}
if (bin[list] == "")
{
bin[list] = "0";
}
bin[list]=bin[list].Substring(1,bin[list].Length-1);
for (k=0; k<n; k++) // inside 01
{
jack[k]=Convert.ToInt32(bin[list].Substring(k,1));
quality[list]=quality[list]+mass[k]*jack[k]*cost[k]; 	// integral of costs
amount[list]=amount[list]+mass[k]*jack[k]; 	// integral of mass
}
if (amount[list]<= Inside)		// current mass < Knapsack
{
Console.WriteLine("{0} {1} {2} {3}", Inside, amount[list], quality[list], bin[list]);
}
}
Console.WriteLine();

max=0;
max_num=1;
for (i=0; i < all; i++)
{
if (amount[i]<=Inside && quality[i]>max)
{
max = quality[i]; max_num =i ;
}
}
Console.WriteLine("{0} {1} {2}",amount[max_num],quality[max_num],bin[max_num]);
}
}
}
Output:
# Mass Cost
1 2 12
2 3 17
3 1 14
4 3 17
5 1 13
Chifer Mass Cost
11000 5 5 75
01001 5 4 64
00111 5 5 78 !!!
00110 5 4 65
00101 5 2 27
Mass MAX Chifer
5 78 00111
Output:
int n = 20;
int Inside = 400;
int all=Convert.ToInt32(Math.Pow(2,(n+1)));
int[] mass = {9,13,153,50,15,68,27,39,23,52,11,32,24,48,73,42,43,22,7,4,30};
int[] cost = {150,35,200,160,60,45,60,40,30,10,70,30,15,10,40,70,75,80,20,50,10};

396 1030 11111010001000011111

jdoodle.com/ia/rSn

## C++

### First version

Library: Boost
#include <vector>
#include <string>
#include <iostream>
#include <boost/tuple/tuple.hpp>
#include <set>

int findBestPack( const std::vector<boost::tuple<std::string , int , int> > & ,
std::set<int> & , const int  ) ;

int main( ) {
std::vector<boost::tuple<std::string , int , int> > items ;
//===========fill the vector with data====================
items.push_back( boost::make_tuple( "" , 0  ,  0 ) ) ;
items.push_back( boost::make_tuple( "map" , 9 , 150 ) ) ;
items.push_back( boost::make_tuple( "compass" , 13 , 35 ) ) ;
items.push_back( boost::make_tuple( "water" , 153 , 200 ) ) ;
items.push_back( boost::make_tuple( "sandwich", 50 , 160 ) ) ;
items.push_back( boost::make_tuple( "glucose" , 15 , 60 ) ) ;
items.push_back( boost::make_tuple( "tin", 68 , 45 ) ) ;
items.push_back( boost::make_tuple( "banana", 27 , 60 ) ) ;
items.push_back( boost::make_tuple( "apple" , 39 , 40 ) ) ;
items.push_back( boost::make_tuple( "cheese" , 23 , 30 ) ) ;
items.push_back( boost::make_tuple( "beer" , 52 , 10 ) ) ;
items.push_back( boost::make_tuple( "suntan creme" , 11 , 70 ) ) ;
items.push_back( boost::make_tuple( "camera" , 32 , 30 ) ) ;
items.push_back( boost::make_tuple( "T-shirt" , 24 , 15 ) ) ;
items.push_back( boost::make_tuple( "trousers" , 48 , 10 ) ) ;
items.push_back( boost::make_tuple( "umbrella" , 73 , 40 ) ) ;
items.push_back( boost::make_tuple( "waterproof trousers" , 42 , 70 ) ) ;
items.push_back( boost::make_tuple( "waterproof overclothes" , 43 , 75 ) ) ;
items.push_back( boost::make_tuple( "note-case" , 22 , 80 ) ) ;
items.push_back( boost::make_tuple( "sunglasses" , 7 , 20 ) ) ;
items.push_back( boost::make_tuple( "towel" , 18 , 12 ) ) ;
items.push_back( boost::make_tuple( "socks" , 4 , 50 ) ) ;
items.push_back( boost::make_tuple( "book" , 30 , 10 ) ) ;
const int maximumWeight = 400 ;
std::set<int> bestItems ; //these items will make up the optimal value
int bestValue = findBestPack( items , bestItems , maximumWeight ) ;
std::cout << "The best value that can be packed in the given knapsack is " <<
bestValue << " !\n" ;
int totalweight = 0 ;
std::cout << "The following items should be packed in the knapsack:\n" ;
for ( std::set<int>::const_iterator si = bestItems.begin( ) ;
si != bestItems.end( ) ; si++ ) {
std::cout << (items.begin( ) + *si)->get<0>( ) << "\n" ;
totalweight += (items.begin( ) + *si)->get<1>( ) ;
}
std::cout << "The total weight of all items is " << totalweight << " !\n" ;
return 0 ;
}

int findBestPack( const std::vector<boost::tuple<std::string , int , int> > & items ,std::set<int> & bestItems , const int weightlimit ) {
//dynamic programming approach sacrificing storage space for execution
//time , creating a table of optimal values for every weight and a
//second table of sets with the items collected so far in the knapsack
//the best value is in the bottom right corner of the values table,
//the set of items in the bottom right corner of the sets' table.
const int n = items.size( ) ;
int bestValues [ n ][ weightlimit ] ;
std::set<int> solutionSets[ n ][ weightlimit ] ;
std::set<int> emptyset ;
for ( int i = 0 ; i < n ; i++ ) {
for ( int j = 0 ; j < weightlimit  ; j++ ) {
bestValues[ i ][ j ] = 0 ;
solutionSets[ i ][ j ] = emptyset ;
}
}
for ( int i = 0 ; i < n ; i++ ) {
for ( int weight = 0 ; weight < weightlimit ; weight++ ) {
if ( i == 0 )
bestValues[ i ][ weight ] = 0 ;
else  {
int itemweight = (items.begin( ) + i)->get<1>( ) ;
if ( weight < itemweight ) {
bestValues[ i ][ weight ] = bestValues[ i - 1 ][ weight ] ;
solutionSets[ i ][ weight ] = solutionSets[ i - 1 ][ weight ] ;
} else { // weight >= itemweight
if ( bestValues[ i - 1 ][ weight - itemweight ] +
(items.begin( ) + i)->get<2>( ) >
bestValues[ i - 1 ][ weight ] ) {
bestValues[ i ][ weight ] =
bestValues[ i - 1 ][ weight - itemweight ] +
(items.begin( ) + i)->get<2>( ) ;
solutionSets[ i ][ weight ] =
solutionSets[ i - 1 ][ weight - itemweight ] ;
solutionSets[ i ][ weight ].insert( i ) ;
}
else {
bestValues[ i ][ weight ] = bestValues[ i - 1 ][ weight ] ;
solutionSets[ i ][ weight ] = solutionSets[ i - 1 ][ weight ] ;
}
}
}
}
}
bestItems.swap( solutionSets[ n - 1][ weightlimit - 1 ] ) ;
return bestValues[ n - 1 ][ weightlimit - 1 ] ;
}
Output:
The best value that can be packed in the given knapsack is 1030 !
The following items should be packed in the knapsack:
map
compass
water
sandwich
glucose
banana
suntan creme
waterproof trousers
waterproof overclothes
note-case
sunglasses
socks
The total weight of all items is 396 !

### Second version

Works with: C++17
#include <iomanip>
#include <iostream>
#include <set>
#include <string>
#include <tuple>
#include <vector>

std::tuple<std::set<int>, int> findBestPack(const std::vector<std::tuple<std::string, int, int> > &items, const int weightlimit) {
const auto n = items.size();
int bestValues[n][weightlimit] = { 0 };
std::set<int> solutionSets[n][weightlimit];
std::set<int> bestItems;
for (auto i = 0u; i < n; i++)
for (auto weight = 0; weight < weightlimit; weight++) {
if (i == 0)
bestValues[i][weight] = 0;
else {
auto [_, itemweight, value] = *(items.begin() + i);
if (weight < itemweight) {
bestValues[i][weight] = bestValues[i - 1][weight];
solutionSets[i][weight] = solutionSets[i - 1][weight];
} else {
if (bestValues[i - 1][weight - itemweight] + value > bestValues[i - 1][weight]) {
bestValues[i][weight] = bestValues[i - 1][weight - itemweight] + value;
solutionSets[i][weight] = solutionSets[i - 1][weight - itemweight];
solutionSets[i][weight].insert(i);
} else {
bestValues[i][weight] = bestValues[i - 1][weight];
solutionSets[i][weight] = solutionSets[i - 1][weight];
}
}
}
}

bestItems.swap(solutionSets[n - 1][weightlimit - 1]);
return { bestItems, bestValues[n - 1][weightlimit - 1] };
}

int main() {
const std::vector<std::tuple<std::string, int, int>> items = {
{ "", 0, 0 },
{ "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 creme", 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 } };

const int maximumWeight = 400;
const auto &[bestItems, bestValue] = findBestPack(items, maximumWeight);
int totalweight = 0;
std::cout << std::setw(24) << "best knapsack:" << std::endl;
for (auto si = bestItems.begin(); si != bestItems.end(); si++) {
auto [name, weight, value] = *(items.begin() + *si);
std::cout << std::setw(24) << name << std::setw(6) << weight << std::setw(6) << value << std::endl;
totalweight += weight;
}
std::cout << std::endl << std::setw(24) << "total:" << std::setw(6) << totalweight << std::setw(6) << bestValue << std::endl;
return 0;
}
Output:
best knapsack:
map     9   150
compass    13    35
water   153   200
sandwich    50   160
glucose    15    60
banana    27    60
suntan creme    11    70
waterproof trousers    42    70
waterproof overclothes    43    75
note-case    22    80
sunglasses     7    20
socks     4    50

total:   396  1030

## C_sharp

All combinations, eight threads, break when weight is to large.

using System;  // 4790@3.6
class Program
{
static void Main()
{
var sw = System.Diagnostics.Stopwatch.StartNew();
Console.Write(knapSack(400) + "\n" + sw.Elapsed);  // 60 ms
}

static string knapSack(uint w1)
{
uint sol = 0, v1 = 0;
Parallel.For(1, 9, t =>
{
uint j, wi, k, vi, i1 = 1u << w.Length;
for (uint i = (uint)t; i < i1; i += 8)
{
k = wi = vi = 0;
for (j = i; j > 0; j >>= 1, k++)
if ((j & 1) > 0)
{
if ((wi += w[k]) > w1) break;
vi += v[k];
}
if (wi <= w1 && v1 < vi)
lock (locker)
if (v1 < vi) { v1 = vi; sol = i; }
}
});
string str = "";
for (uint k = 0; sol > 0; sol >>= 1, k++)
if ((sol & 1) > 0) str += items[k] + "\n";
return str;
}

static readonly object locker = new object();

static byte[] w = { 9, 13, 153, 50, 15, 68, 27, 39, 23, 52, 11,
32, 24, 48, 73, 42, 43, 22, 7, 18, 4, 30 },

v = { 150, 35, 200, 160, 60, 45, 60, 40, 30, 10, 70,
30, 15, 10, 40, 70, 75, 80, 20, 12, 50, 10 };

static string[] items = {"map","compass","water","sandwich","glucose","tin",
"banana","apple","cheese","beer","suntan cream",
"camera","T-shirt","trousers","umbrella",
"waterproof trousers","waterproof overclothes",
"note-case","sunglasses","towel","socks","book"};
}

A dynamic version.

using System
class program
{
static void Main()
{
knapSack(40);
var sw = System.Diagnostics.Stopwatch.StartNew();
Console.Write(knapSack(400) + "\n" + sw.Elapsed);  // 31 µs
}

static string knapSack(uint w1)
{
uint n = (uint)w.Length; var K = new uint[n + 1, w1 + 1];
for (uint vi, wi, w0, x, i = 0; i < n; i++)
for (vi = v[i], wi = w[i], w0 = 1; w0 <= w1; w0++)
{
x = K[i, w0];
if (wi <= w0) x = max(vi + K[i, w0 - wi], x);
K[i + 1, w0] = x;
}
string str = "";
for (uint v1 = K[n, w1]; v1 > 0; n--)
if (v1 != K[n - 1, w1])
{
v1 -= v[n - 1]; w1 -= w[n - 1]; str += items[n - 1] + "\n";
}
return str;
}

static uint max(uint a, uint b) { return a > b ? a : b; }

static byte[] w =  { 9, 13, 153, 50, 15, 68, 27, 39, 23, 52, 11,
32, 24, 48, 73, 42, 43, 22, 7, 18, 4, 30 },

v =  { 150, 35, 200, 160, 60, 45, 60, 40, 30, 10, 70,
30, 15, 10, 40, 70, 75, 80, 20, 12, 50, 10 };

static string[] items =  {"map","compass","water","sandwich","glucose","tin",
"banana","apple","cheese","beer","suntan cream",
"camera","T-shirt","trousers","umbrella",
"waterproof trousers","waterproof overclothes",
"note-case","sunglasses","towel","socks","book"};
}

## Ceylon

module.ceylon:

module knapsack "1.0.0" {
}

run.ceylon:

shared void run() {
value knapsack = pack(items, empty(400));

print(knapsack);
}

class Item(name,weight,theValue) {
String name;
shared Integer weight;
shared Float theValue;

shared actual String string = "item(``name``, ``weight``, ``theValue``)";
}

class Knapsack(items,theValue,weight,available) {
shared Item[] items;
shared Float theValue;
shared Integer weight;
shared Integer available;

shared Boolean canAccept(Item item)
=> item.weight <= available;

String itemsString = items.fold("")((total, remaining) => "``total``\t\n``remaining.string``" );

shared actual String string = "Total value: ``theValue``\nTotal weight: ``weight``\nItems:\n``itemsString``";
}

Knapsack empty(Integer capacity)
=> Knapsack([], 0.0, 0, capacity);

Item[] items =
[
Item("map", 9, 150.0),
Item("compass", 13, 35.0),
Item("water", 153, 200.0),
Item("sandwich", 50, 160.0),
Item("glucose", 15, 60.0),
Item("tin", 68, 45.0),
Item("banana", 27, 60.0),
Item("apple", 39, 40.0),
Item("cheese", 23, 30.0),
Item("beer", 52, 10.0),
Item("cream", 11, 70.0),
Item("camera", 32, 30.0),
Item("tshirt", 24, 15.0),
Item("trousers", 48, 10.0),
Item("umbrella", 73, 40.0),
Item("trousers", 42, 70.0),
Item("overclothes", 43, 75.0),
Item("notecase", 22, 80.0),
Item("sunglasses", 7, 20.0),
Item("towel", 18, 12.0),
Item("socks", 4, 50.0),
Item("book", 30, 10.0)
];

=> Knapsack { items = knapsack.items.withTrailing(item);
theValue = knapsack.theValue + item.theValue;
weight = knapsack.weight + item.weight;
available = knapsack.available - item.weight; };

Float rating(Item item) => item.theValue / item.weight.float;

Knapsack pack(Item[] items, Knapsack knapsack)
// Sort the items by decreasing rating, that is, value divided by weight
=> let (itemsSorted =
items.group(rating)
.sort(byDecreasing((Float->[Item+] entry) => entry.key))
.map(Entry.item)
.flatMap((element) => element)
.sequence())

packRecursive(itemsSorted,knapsack);

Knapsack packRecursive(Item[] sortedItems, Knapsack knapsack)
=> if (exists firstItem=sortedItems.first, knapsack.canAccept(firstItem))
else knapsack;

Output:
Total value: 1030.0
Total weight: 396
Items:

item(map, 9, 150.0)
item(socks, 4, 50.0)
item(cream, 11, 70.0)
item(glucose, 15, 60.0)
item(notecase, 22, 80.0)
item(sandwich, 50, 160.0)
item(sunglasses, 7, 20.0)
item(compass, 13, 35.0)
item(banana, 27, 60.0)
item(overclothes, 43, 75.0)
item(trousers, 42, 70.0)
item(water, 153, 200.0)

## Clojure

Uses the dynamic programming solution from Wikipedia. First define the items data:

(def item-data
[ "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])

(defstruct item :name :weight :value)

(def items (vec (map #(apply struct item %) (partition 3 item-data))))

m is as per the Wikipedia formula, except that it returns a pair [value indexes] where indexes is a vector of index values in items. value is the maximum value attainable using items 0..i whose total weight doesn't exceed w; indexes are the item indexes that produces the value.

(declare mm) ;forward decl for memoization function

(defn m [i w]
(cond
(< i 0) [0 []]
(= w 0) [0 []]
:else
(let [{wi :weight vi :value} (get items i)]
(if (> wi w)
(mm (dec i) w)
(let [[vn sn :as no]  (mm (dec i) w)
[vy sy :as yes] (mm (dec i) (- w wi))]
(if (> (+ vy vi) vn)
[(+ vy vi) (conj sy i)]
no))))))

(def mm (memoize m))

Call m and print the result:

(use '[clojure.string :only [join]])

(let [[value indexes] (m (-> items count dec) 400)
names (map (comp :name items) indexes)]
(println "items to pack:" (join ", " names))
(println "total value:" value)
(println "total weight:" (reduce + (map (comp :weight items) indexes))))
Output:
items to pack: map, compass, water, sandwich, glucose, banana, suntan cream, waterproof trousers,
waterproof overclothes, note-case, sunglasses, socks
total value: 1030
total weight: 396

## Common Lisp

Cached method.

;;; 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))))
(if (> w spc) x
(let* ((y (knapsack1 (- spc w) (cdr items)))
(v (+ v (first y))))
(if (< v (first x)) x
(list v (+ w (second y)) (cons i (third y))))))))))

(knapsack1 max-weight items))))

(print
(knapsack 400
'((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) (cream 11 70) (camera 32 30)
(T-shirt 24 15) (trousers 48 10) (umbrella 73 40)
(trousers 42 70) (overclothes 43 75) (notecase 22 80)
(glasses 7 20) (towel 18 12) (socks 4 50) (book 30 10))))
Output:
(1030 396
((MAP 9 150) (COMPASS 13 35) (WATER 153 200) (SANDWICH 50 160) (GLUCOSE 15 60)
(BANANA 27 60) (CREAM 11 70) (TROUSERS 42 70) (OVERCLOTHES 43 75)
(NOTECASE 22 80) (GLASSES 7 20) (SOCKS 4 50)))

## Crystal

Branch and bound solution

require "bit_array"

struct BitArray
def clone
BitArray.new(size).tap { |new| new.to_slice.copy_from (to_slice) }
end
end

record Item, name : String, weight : Int32, value : Int32

record Selection, mask : BitArray, cur_index : Int32, total_value : Int32

class Knapsack
@threshold_value = 0
@threshold_choice : Selection?
getter checked_nodes = 0

def knapsack_step(taken, items, remaining_weight)
if taken.total_value > @threshold_value
@threshold_value = taken.total_value
@threshold_choice = taken
end
candidate_index = items.index(taken.cur_index) { |item| item.weight <= remaining_weight }
return nil unless candidate_index
@checked_nodes += 1
candidate = items[candidate_index]
# candidate is a best of available items, so if we fill remaining value with it
# and still don't reach the threshold, the branch is wrong
return nil if taken.total_value + 1.0 * candidate.value / candidate.weight * remaining_weight < @threshold_value
# now recursively check both variants
knapsack_step Selection.new(mask, candidate_index + 1, taken.total_value + candidate.value), items, remaining_weight - candidate.weight
knapsack_step Selection.new(mask, candidate_index + 1, taken.total_value), items, remaining_weight
end

def select(items, max_weight)
@checked_variants = 0
# sort by descending relative value
list = items.sort_by { |item| -1.0 * item.value / item.weight }
# use heuristic of relative value as an initial estimate for branch&bounds
w = max_weight
heur_list = list.take_while { |item| w -= item.weight; w > 0 }
nothing = Selection.new(BitArray.new(items.size), 0, 0)
@threshold_value = heur_list.sum(&.value) - 1
@threshold_choice = nothing
knapsack_step(nothing, list, max_weight)
selected = @threshold_choice.not_nil!
result = [] of Item
selected.mask.each_with_index { |v, i| result << list[i] if v }
result
end
end

possible = [
Item.new("map", 9, 150),
Item.new("compass", 13, 35),
Item.new("water", 153, 200),
Item.new("sandwich", 50, 160),
Item.new("glucose", 15, 60),
Item.new("tin", 68, 45),
Item.new("banana", 27, 60),
Item.new("apple", 39, 40),
Item.new("cheese", 23, 30),
Item.new("beer", 52, 10),
Item.new("suntan cream", 11, 70),
Item.new("camera", 32, 30),
Item.new("T-shirt", 24, 15),
Item.new("trousers", 48, 10),
Item.new("umbrella", 73, 40),
Item.new("waterproof trousers", 42, 70),
Item.new("waterproof overclothes", 43, 75),
Item.new("note-case", 22, 80),
Item.new("sunglasses", 7, 20),
Item.new("towel", 18, 12),
Item.new("socks", 4, 50),
Item.new("book", 30, 10),
]

solver = Knapsack.new
used = solver.select(possible, 400)
puts "optimal choice: #{used.map(&.name)}"
puts "total weight #{used.sum(&.weight)}, total value #{used.sum(&.value)}"
puts "checked nodes: #{solver.checked_nodes}"
Output:
optimal choice: ["map", "socks", "suntan cream", "glucose", "note-case", "sandwich", "sunglasses", "compass", "banana", "waterproof overclothes", "waterproof trousers", "water"]
total weight 396, total value 1030
checked nodes: 992

## D

### Dynamic Programming Version

Translation of: Python
import std.stdio, std.algorithm, std.typecons, std.array, std.range;

struct Item { string name; int weight, value; }

Item[] knapsack01DinamicProgramming(immutable Item[] items, in int limit)
pure nothrow @safe {
auto tab = new int[][](items.length + 1, limit + 1);

foreach (immutable i, immutable it; items)
foreach (immutable w; 1 .. limit + 1)
tab[i + 1][w] = (it.weight > w) ? tab[i][w] :
max(tab[i][w], tab[i][w - it.weight] + it.value);

typeof(return) result;
int w = limit;
foreach_reverse (immutable i, immutable it; items)
if (tab[i + 1][w] != tab[i][w]) {
w -= it.weight;
result ~= it;
}

return result;
}

void main() @safe {
enum int limit = 400;
immutable Item[] items = [
{"apple",      39,  40}, {"banana",        27,  60},
{"beer",       52,  10}, {"book",          30,  10},
{"camera",     32,  30}, {"cheese",        23,  30},
{"compass",    13,  35}, {"glucose",       15,  60},
{"map",         9, 150}, {"note-case",     22,  80},
{"sandwich",   50, 160}, {"socks",          4,  50},
{"sunglasses",  7,  20}, {"suntan cream",  11,  70},
{"t-shirt",    24,  15}, {"tin",           68,  45},
{"towel",      18,  12}, {"trousers",      48,  10},
{"umbrella",   73,  40}, {"water",        153, 200},
{"waterproof overclothes", 43, 75},
{"waterproof trousers",    42, 70}];

immutable bag = knapsack01DinamicProgramming(items, limit);
writefln("Items:\n%-(  %s\n%)", bag.map!q{ a.name }.retro);
const t = reduce!q{ a[] += [b.weight, b.value] }([0, 0], bag);
writeln("\nTotal weight and value: ", t[0] <= limit ? t : [0, 0]);
}
Output:
Items:
banana
compass
glucose
map
note-case
sandwich
socks
sunglasses
suntan cream
water
waterproof overclothes
waterproof trousers

Total weight and value: [396, 1030]

### Brute Force Version

Translation of: C
struct Item { string name; int weight, value; }

immutable Item[] items = [
{"apple",      39,  40}, {"banana",        27,  60},
{"beer",       52,  10}, {"book",          30,  10},
{"camera",     32,  30}, {"cheese",        23,  30},
{"compass",    13,  35}, {"glucose",       15,  60},
{"map",         9, 150}, {"note-case",     22,  80},
{"sandwich",   50, 160}, {"socks",          4,  50},
{"sunglasses",  7,  20}, {"suntan cream",  11,  70},
{"t-shirt",    24,  15}, {"tin",           68,  45},
{"towel",      18,  12}, {"trousers",      48,  10},
{"umbrella",   73,  40}, {"water",        153, 200},
{"waterproof overclothes", 43, 75},
{"waterproof trousers",    42, 70}];

struct Solution { uint bits; int value; }
static assert(items.length <= Solution.bits.sizeof * 8);

void solve(in int weight, in int idx, ref Solution s)
pure nothrow @nogc @safe {
if (idx < 0) {
s.bits = s.value = 0;
return;
}

if (weight < items[idx].weight) {
solve(weight, idx - 1, s);
return;
}

Solution v1, v2;
solve(weight, idx - 1, v1);
solve(weight - items[idx].weight, idx - 1, v2);

v2.value += items[idx].value;
v2.bits |= (1 << idx);

s = (v1.value >= v2.value) ? v1 : v2;
}

void main() @safe {
import std.stdio;

auto s = Solution(0, 0);
solve(400, items.length - 1, s);

writeln("Items:");
int w = 0;
foreach (immutable i, immutable it; items)
if (s.bits & (1 << i)) {
writeln("  ", it.name);
w += it.weight;
}
writefln("\nTotal value: %d; weight: %d", s.value, w);
}

The runtime is about 0.09 seconds.

Output:
Items:
banana
compass
glucose
map
note-case
sandwich
socks
sunglasses
suntan cream
water
waterproof overclothes
waterproof trousers

Total value: 1030; weight: 396

### Short Dynamic Programming Version

import std.stdio, std.algorithm, std.typecons, std.array, std.range;

struct Item { string name; int w, v; }
alias Pair = Tuple!(int,"tot", string[],"names");

immutable Item[] items = [{"apple",39,40}, {"banana", 27, 60},
{"beer", 52, 10}, {"book", 30, 10}, {"camera", 32, 30},
{"cheese", 23, 30}, {"compass", 13, 35}, {"glucose", 15, 60},
{"map", 9, 150}, {"note-case", 22, 80}, {"sandwich", 50, 160},
{"socks", 4, 50}, {"sunglasses", 7, 20}, {"suntan cream", 11, 70},
{"t-shirt", 24, 15}, {"tin", 68, 45}, {"towel", 18, 12},
{"trousers", 48, 10}, {"umbrella", 73, 40}, {"water", 153, 200},
{"overclothes", 43, 75}, {"waterproof trousers", 42, 70}];

auto addItem(Pair[] lst, in Item it) pure /*nothrow*/ {
auto aux = lst.map!(vn => Pair(vn.tot + it.v, vn.names ~ it.name));
return lst[0..it.w] ~ lst[it.w..\$].zip(aux).map!q{ a[].max }.array;
}

void main() {
}

Output:
Tuple!(int, "tot", string[], "names")(1030, ["banana", "compass", "glucose", "map", "note-case", "sandwich", "socks", "sunglasses", "suntan cream", "water", "overclothes", "waterproof trousers"])

## Dart

List solveKnapsack(items, maxWeight) {
int MIN_VALUE=-100;
int N = items.length; // number of items
int W = maxWeight; // maximum weight of knapsack

List profit = new List(N+1);
List weight = new List(N+1);

// generate random instance, items 1..N
for(int n = 1; n<=N; n++) {
profit[n] = items[n-1][2];
weight[n] = items[n-1][1];

}

// opt[n][w] = max profit of packing items 1..n with weight limit w
// sol[n][w] = does opt solution to pack items 1..n with weight limit w include item n?
List<List<int>> opt = new List<List<int>>(N+1);
for (int i=0; i<N+1; i++) {
opt[i] = new List<int>(W+1);
for(int j=0; j<W+1; j++) {
opt[i][j] = MIN_VALUE;
}
}

List<List<bool>> sol = new List<List<bool>>(N+1);
for (int i=0; i<N+1; i++) {
sol[i] = new List<bool>(W+1);
for(int j=0; j<W+1; j++) {
sol[i][j] = false;
}
}

for(int n=1; n<=N; n++) {
for (int w=1; w <= W; w++) {
// don't take item n
int option1 = opt[n-1][w];

// take item n
int option2 = MIN_VALUE;
if (weight[n] <= w) {
option2 = profit[n] + opt[n-1][w - weight[n]];
}

// select better of two options
opt[n][w] = Math.max(option1, option2);
sol[n][w] = (option2 > option1);
}
}

// determine which items to take
List<List> packItems = new List<List>();
List<bool> take = new List(N+1);
for (int n = N, w = W; n > 0; n--) {
if (sol[n][w]) {
take[n] = true;
w = w - weight[n];
} else {
take[n] = false;
}
}

return packItems;

}

main() {
List knapsackItems = [];
int maxWeight = 400;
Stopwatch sw = new Stopwatch.start();
List p = solveKnapsack(knapsackItems, maxWeight);
sw.stop();
int totalWeight = 0;
int totalValue = 0;
print(["item","profit","weight"]);
p.forEach((var i) { print("\${i}"); totalWeight+=i[1]; totalValue+=i[2]; });
print("Total Value = \${totalValue}");
print("Total Weight = \${totalWeight}");
print("Elapsed Time = \${sw.elapsedInMs()}ms");

}
Output:
[item, profit, weight]
[socks, 4, 50]
[sunglasses, 7, 20]
[note-case, 22, 80]
[waterproof overclothes, 43, 75]
[waterproof trousers, 42, 70]
[suntan cream, 11, 70]
[banana, 27, 60]
[glucose, 15, 60]
[sandwich, 50, 160]
[water, 153, 200]
[compass, 13, 35]
[map, 9, 150]
Total Value = 1030
Total Weight = 396
Elapsed Time = 6ms

## EasyLang

name\$[] = [ "map" "compass" "water" "sandwich" "glucose" "tin" "banana" "apple" "cheese" "beer" "suntan cream" "camera" "t-shirt" "trousers" "umbrella" "waterproof trousers" "waterproof overclothes" "note-case" "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 160 60 45 60 40 30 10 70 30 15 10 40 70 75 80 20 12 50 10 ]
max_w = 400
#
func solve i maxw . items[] wres vres .
if i <= 0
wres = 0
vres = 0
items[] = [ ]
elif weight[i] > maxw
call solve i - 1 maxw items[] wres vres
else
call solve i - 1 maxw items[] wres vres
call solve i - 1 maxw - weight[i] items1[] w1 v1
v1 += value[i]
if v1 > vres
swap items[] items1[]
items[] &= i
wres = w1 + weight[i]
vres = v1
.
.
.
call solve len weight[] max_w items[] w v
print "weight: " & w
print "value: " & v
print "items:"
for i = 1 to len items[]
print "  " & name\$[items[i]]
.

## EchoLisp

(require 'struct)
(require 'hash)
(require 'sql)

(define H (make-hash))
(define T (make-table (struct goodies (name poids valeur ))))
(define-syntax-rule (name i) (table-xref T i 0))
(define-syntax-rule (poids i) (table-xref T i 1))
(define-syntax-rule (valeur i) (table-xref T i 2))

;;  make an unique hash-key from (i rest)
(define (t-idx i r)  (string-append i "|" r))
;; retrieve best score for item i, remaining r availbble weight
(define (t-get i r)  (or (hash-ref H (t-idx i r)) 0))

;; compute best score (i), assuming best (i-1 rest) is known
(define (score i restant)
(if (< i 0) 0
(hash-ref! H (t-idx i restant)
(if ( >= restant (poids i))
(max
(score (1- i) restant)
(+ (score (1- i) (- restant (poids i))) (valeur i)))
(score (1- i) restant)))))

;; compute best scores, starting from last item
(define restant W)
(define N (1- (table-count T)))
(writeln 'total-value (score N W))
(for/list  ((i (in-range N -1 -1)))
#:continue (= (t-get i restant) (t-get (1- i) restant))
(set! restant (- restant (poids i)))
(name i)))
Output:
;; init table
(define goodies
'((map 9 150) ; 9 is weight, 150 is value
(compass 13 35) (water 153 200) (sandwich 50 160)
(glucose 15 60) (tin 68 45)(banana 27 60) (apple 39 40)
(fromage 23 30) (beer 52 10) (🌞-suntan-cream 11 70) (camera 32 30)
(T-shirt 24 15) (pantalons 48 10) (umbrella 73 40)
(☔️-trousers 42 70) (☔️-overclothes 43 75) (note-case 22 80)
(🌞-sun-glasses 7 20) (towel 18 12) (socks 4 50) (book 30 10)))
(list->table goodies T)

total-value     1030
(socks 🌞-sun-glasses note-case ☔️-overclothes ☔️-trousers 🌞-suntan-cream banana
glucose sandwich water compass map)

(length (hash-keys H))
4939  ;; number of entries "i | weight" in hash table

## Eiffel

class
APPLICATION

create
make

feature {NONE} -- Initialization

make
local
knapsack: KNAPSACKZEROONE
do
create knapsack.make (400)
knapsack.add_item (create {ITEM}.make ("", 0, 0))
knapsack.add_item (create {ITEM}.make ("map", 9, 150))
knapsack.add_item (create {ITEM}.make ("compass", 13, 35))
knapsack.add_item (create {ITEM}.make ("water", 153, 200))
knapsack.add_item (create {ITEM}.make ("sandwich", 50, 160))
knapsack.add_item (create {ITEM}.make ("glucose", 15, 60))
knapsack.add_item (create {ITEM}.make ("tin", 68, 45))
knapsack.add_item (create {ITEM}.make ("banana", 27, 60))
knapsack.add_item (create {ITEM}.make ("apple", 39, 40))
knapsack.add_item (create {ITEM}.make ("cheese", 23, 30))
knapsack.add_item (create {ITEM}.make ("beer", 52, 10))
knapsack.add_item (create {ITEM}.make ("suntan cream", 11, 70))
knapsack.add_item (create {ITEM}.make ("camera", 32, 30))
knapsack.add_item (create {ITEM}.make ("T-shirt", 24, 15))
knapsack.add_item (create {ITEM}.make ("trousers", 48, 10))
knapsack.add_item (create {ITEM}.make ("umbrella, ella ella", 73, 40))
knapsack.add_item (create {ITEM}.make ("waterproof trousers", 42, 70))
knapsack.add_item (create {ITEM}.make ("waterproof overclothes", 43, 75))
knapsack.add_item (create {ITEM}.make ("note-case", 22, 80))
knapsack.add_item (create {ITEM}.make ("sunglasses", 7, 20))
knapsack.add_item (create {ITEM}.make ("towel", 18, 12))
knapsack.add_item (create {ITEM}.make ("socks", 4, 50))
knapsack.add_item (create {ITEM}.make ("book", 30, 10))
knapsack.compute_solution
end

end
class
ITEM

create
make, make_from_other

feature

name: STRING

weight: INTEGER

value: INTEGER

make_from_other (other: ITEM)
-- Item with name, weight and value set to 'other's name, weight and value.
do
name := other.name
weight := other.weight
value := other.value
end

make (a_name: String; a_weight, a_value: INTEGER)
-- Item with name, weight and value set to 'a_name', 'a_weight' and 'a_value'.
require
a_name /= Void
a_weight >= 0
a_value >= 0
do
name := a_name
weight := a_weight
value := a_value
end

end
class
KNAPSACKZEROONE

create
make

feature

items: ARRAY [ITEM]

max_weight: INTEGER

feature

make (a_max_weight: INTEGER)
-- Make an empty knapsack.
require
a_max_weight >= 0
do
create items.make_empty
max_weight := a_max_weight
end

local
temp: ITEM
do
create temp.make_from_other (item)
items.force (item, items.count + 1)
end

compute_solution
local
M: ARRAY [INTEGER]
n: INTEGER
i, j: INTEGER
w_i, v_i: INTEGER
item_i: ITEM
do
n := items.count
create M.make_filled (0, 1, n * max_weight)
from
i := 2
until
(i > n)
loop
from
j := 1
until
j > max_weight
loop
item_i := items [i]
w_i := item_i.weight
if w_i <= j then
v_i := item_i.value
M [(i - 1) * max_weight + j] := max (M [(i - 2) * max_weight + j], M [(i - 2) * max_weight + j - w_i + 1] + v_i)
else
M [(i - 1) * max_weight + j] := M [(i - 2) * max_weight + j]
end
j := j + 1
end
i := i + 1
end
io.put_string ("The final value of the knapsack will be: ")
io.put_integer (M [(n - 1) * max_weight + max_weight]);
io.new_line
--compute the items that fit into the knapsack
create final_items.make
io.put_string ("We'll take the following items: %N");
from
i := n
j := max_weight
until
i <= 1 or j <= 1
loop
item_i := items [i]
w_i := item_i.weight
if w_i <= j then
v_i := item_i.value
if M [(i - 1) * max_weight + j] = M [(i - 2) * max_weight + j] then
else
final_items.extend (item_i)
io.put_string (item_i.name)
io.new_line
j := j - w_i
end
else
end
i := i - 1
end
end

feature {NONE}

max (a, b: INTEGER): INTEGER
-- Max of 'a' and 'b'.
do
Result := a
if a < b then
Result := b
end
end

end
Output:
The final value of the knapsack will be: 1030
We'll take the following items:
socks
sunglasses
note-case
waterproof overclothes
waterproof trousers
suntan cream
banana
glucose
sandwich
water
compass
map

## Elixir

Translation of: Erlang
defmodule Knapsack do
def solve([], _total_weight, item_acc, value_acc, weight_acc), do:
{item_acc, value_acc, weight_acc}
def solve([{_item, item_weight, _item_value} | t],
total_weight,
item_acc,
value_acc,
weight_acc) when item_weight > total_weight, do:
solve(t, total_weight, item_acc, value_acc, weight_acc)
def solve([{item_name, item_weight, item_value} | t],
total_weight,
item_acc,
value_acc,
weight_acc) do
{_tail_item_acc, tail_value_acc, _tail_weight_acc} = tail_res =
solve(t, total_weight, item_acc, value_acc, weight_acc)
solve(t,
total_weight - item_weight,
[item_name | item_acc],
value_acc + item_value,
weight_acc + item_weight)
end
end

stuff = [{"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}]
max_weight = 400

go = fn (stuff, max_weight) ->
{time, {item_list, total_value, total_weight}} = :timer.tc(fn ->
Knapsack.solve(stuff, max_weight, [], 0, 0)
end)
IO.puts "Items:"
Enum.each(item_list, fn item -> IO.inspect item end)
IO.puts "Total value: #{total_value}"
IO.puts "Total weight: #{total_weight}"
IO.puts "Time elapsed in milliseconds: #{time/1000}"
end
go.(stuff, max_weight)
Output:
Items:
"socks"
"sunglasses"
"note-case"
"waterproof overclothes"
"waterproof trousers"
"suntan cream"
"banana"
"glucose"
"sandwich"
"water"
"compass"
"map"
Total value: 1030
Total weight: 396
Time elapsed in milliseconds: 733.0

## Emacs Lisp

Translation of: Common Lisp
with changes (memoization without macro)
(defun ks (max-w items)
(let ((cache (make-vector (1+ (length items)) nil)))
(dotimes (n (1+ (length items)))
(setf (aref cache n) (make-hash-table :test 'eql)))
(defun ks-emb (spc items)
(let ((slot (gethash spc (aref cache (length items)))))
(cond
((null items) (list 0 0 '()))
(slot slot)
(t (puthash spc
(let*
((i (car items))
(w (nth 1 i))
(v (nth 2 i))
(x (ks-emb spc (cdr items))))
(cond
((> w spc) x)
(t
(let* ((y (ks-emb (- spc w) (cdr items)))
(v (+ v (car y))))
(cond
((< v (car x)) x)
(t
(list v (+ w (nth 1 y)) (cons i (nth 2 y)))))))))
(aref cache (length items)))))))
(ks-emb max-w items)))

(ks 400
'((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) (cream 11 70) (camera 32 30)
(T-shirt 24 15) (trousers 48 10) (umbrella 73 40)
(waterproof-trousers 42 70) (overclothes 43 75) (notecase 22 80)
(glasses 7 20) (towel 18 12) (socks 4 50) (book 30 10)))
Output:
(1030 396 ((map 9 150) (compass 13 35) (water 153 200) (sandwich 50 160) (glucose 15 60)
(banana 27 60) (cream 11 70) (waterproof-trousers 42 70) (overclothes 43 75) (notecase 22 80)
(glasses 7 20) (socks 4 50)))

Another way without cache :

(defun best-rate (l1 l2)
"predicate for sorting a list of elements regarding the value/weight rate"
(let*
((r1 (/ (* 1.0 (nth 2 l1)) (nth 1 l1)))
(r2 (/ (* 1.0 (nth 2 l2)) (nth 1 l2))))
(cond
((> r1 r2) t)
(t nil))))

(defun ks1 (l max)
"return a complete list - complete means 'less than max-weight
but add the next element is impossible'"
(let ((l (sort l 'best-rate)))
(cond
((null l) l)
((<= (nth 1 (car l)) max)
(cons (car l) (ks1 (cdr l) (- max (nth 1 (car l))))))
(t (ks1 (cdr l) max)))))

(defun totval (lol)
"totalize values of a list - lol is not for laughing
but for list of list"
(cond
((null lol) 0)
(t
(+
(nth 2 (car lol))
(totval (cdr lol))))))

(defun ks (l max)
"browse the list to find the best subset to put in the f***ing knapsack"
(cond
((null (cdr l)) (list (car l)))
(t
(let*
((x (ks1 l max))
(y (ks (cdr l) max)))
(cond
((> (totval x) (totval y)) x)
(t y))))))

(ks '((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) (cream 11 70) (camera 32 30)
(T-shirt 24 15) (trousers 48 10) (umbrella 73 40)
(waterproof-trousers 42 70) (overclothes 43 75) (notecase 22 80)
(glasses 7 20) (towel 18 12) (socks 4 50) (book 30 10)) 400)
Output:
with org-babel in Emacs
| map                 |   9 |  150 |
| socks               |   4 |   50 |
| cream               |  11 |   70 |
| glucose             |  15 |   60 |
| notecase            |  22 |   80 |
| sandwich            |  50 |  160 |
| glasses             |   7 |   20 |
| compass             |  13 |   35 |
| banana              |  27 |   60 |
| overclothes         |  43 |   75 |
| waterproof-trousers |  42 |   70 |
| water               | 153 |  200 |
|                     | 396 | 1030 |

## Erlang

-module(knapsack_0_1).

-export([go/0,
solve/5]).

-define(STUFF,
[{"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}
]).

-define(MAX_WEIGHT, 400).

go() ->
StartTime = os:timestamp(),
{ItemList, TotalValue, TotalWeight} =
solve(?STUFF, ?MAX_WEIGHT, [], 0, 0),
TimeElapsed = timer:now_diff(os:timestamp(), StartTime),
io:format("Items: ~n"),
[io:format("~p~n", [Item]) || Item <- ItemList],
io:format(
"Total value: ~p~nTotal weight: ~p~nTime elapsed in milliseconds: ~p~n",
[TotalValue, TotalWeight, TimeElapsed/1000]).

solve([], _TotalWeight, ItemAcc, ValueAcc, WeightAcc) ->
{ItemAcc, ValueAcc, WeightAcc};
solve([{_Item, ItemWeight, _ItemValue} | T],
TotalWeight,
ItemAcc,
ValueAcc,
WeightAcc) when ItemWeight > TotalWeight ->
solve(T, TotalWeight, ItemAcc, ValueAcc, WeightAcc);
solve([{ItemName, ItemWeight, ItemValue} | T],
TotalWeight,
ItemAcc,
ValueAcc,
WeightAcc) ->
{_TailItemAcc, TailValueAcc, _TailWeightAcc} = TailRes =
solve(T, TotalWeight, ItemAcc, ValueAcc, WeightAcc),
solve(T,
TotalWeight - ItemWeight,
[ItemName | ItemAcc],
ValueAcc + ItemValue,
WeightAcc + ItemWeight),

true ->
TailRes;
false ->
end.
Output:
1> knapsack_0_1:go().
Items:
"socks"
"sunglasses"
"note-case"
"waterproof overclothes"
"waterproof trousers"
"suntan cream"
"banana"
"glucose"
"sandwich"
"water"
"compass"
"map"
Total value: 1030
Total weight: 396
Time elapsed in milliseconds: 133.445
ok

## Euler Math Toolbox

>items=["map","compass","water","sandwich","glucose", ...
>  "tin","banana","apple","cheese","beer","suntan creame", ...
>  "camera","t-shirt","trousers","umbrella","waterproof trousers", ...
>  "waterproof overclothes","note-case","sunglasses", ...
>  "towel","socks","book"];
>ws = [9,13,153,50,15,68,27,39,23,52,11, ...
>  32,24,48,73,42,43,22,7,18,4,30];
>vs = [150,35,200,160,60,45,60,40,30,10,70, ...
>  30,15,10,40,70,75,80,20,12,50,10];
>A=ws_id(cols(ws));
>c=vs;
>b=[400]_ones(cols(vs),1);
>sol = intsimplex(A,b,c,eq=-1,>max,>check);
>items[nonzeros(sol)]
map
compass
water
sandwich
glucose
banana
suntan creame
waterproof trousers
waterproof overclothes
note-case
sunglasses
socks

## F#

### Using A* Algorithm

//Solve Knapsack 0-1 using A* algorithm
//Nigel Galloway, August 3rd., 2018
let knapStar items maxW=
let l=List.length items
let p=System.Collections.Generic.SortedSet<float*int*float*float*list<int>>() //H*; level; value of items taken so far; weight so far
let H items maxW=let rec H n g a=match g with |(_,w,v)::e->let t=n+w
if t<=maxW then H t e (a+v) else a+(v/w)*(maxW-n)
|_->a
H 0.0 items 0.0
let pAdd ((h,_,_,_,_) as n) bv=if h>bv then p.Add n |> ignore
let fH n (bv,t) w' v' t'=let _,w,v=List.item n items
let e=max bv (if w<=(maxW-w') then v'+v else bv)
let rt=n::t'
if n+1<l then pAdd ((v'+H (List.skip (n+1) items) maxW),n+1,v',w',t') bv
if w<=(maxW-w') then pAdd ((v'+v+H (List.skip (n+1) items) (maxW-w')),n+1,v'+v,w'+w,rt) bv
if e>bv then (e,rt) else (bv,t)
let rec fN (bv,t)=
let h,zl,zv,zw,zt as r=p.Max
p.Remove r |> ignore
if bv>=h then t else fN (fH zl (bv,t) zw zv zt)
fN (fH 0 (0.0,[]) 0.0 0.0 [])
Output:
let itemsf = [
"map",                     9.0,  150.0;
"compass",                13.0,   35.0;
"water",                 153.0,  200.0;
"sandwich",               50.0,  160.0;
"glucose",                15.0,   60.0;
"tin",                    68.0,   45.0;
"banana",                 27.0,   60.0;
"apple",                  39.0,   40.0;
"cheese",                 23.0,   30.0;
"beer",                   52.0,   10.0;
"suntan cream",           11.0,   70.0;
"camera",                 32.0,   30.0;
"t-shirt",                24.0,   15.0;
"trousers",               48.0,   10.0;
"umbrella",               73.0,   40.0;
"waterproof trousers",    42.0,   70.0;
"waterproof overclothes", 43.0,   75.0;
"note-case",              22.0,   80.0;
"sunglasses",              7.0,   20.0;
"towel",                  18.0,   12.0;
"socks",                   4.0,   50.0;
"book",                   30.0,   10.0;]|> List.sortBy(fun(_,n,g)->n/g)
> let x=knapStar itemsf 400.0;;
> x|>Seq.map (fun n->Seq.item n itemsf)|>Seq.sumBy(fun (_,_,n)->(+n));;
val it : float = 1030.0
> x|>Seq.map (fun n->Seq.item n itemsf)|>Seq.sumBy(fun (_,n,_)->(+n));;
val it : float = 396.0
> x|>Seq.iter(fun n->printfn "%A" (List.item n itemsf));;
("map", 9.0, 150.0)
("socks", 4.0, 50.0)
("suntan cream", 11.0, 70.0)
("glucose", 15.0, 60.0)
("note-case", 22.0, 80.0)
("sandwich", 50.0, 160.0)
("sunglasses", 7.0, 20.0)
("compass", 13.0, 35.0)
("banana", 27.0, 60.0)
("waterproof overclothes", 43.0, 75.0)
("waterproof trousers", 42.0, 70.0)
("water", 153.0, 200.0)

## Factor

Using dynamic programming:

USING: accessors arrays fry io kernel locals make math
math.order math.parser math.ranges sequences sorting ;
IN: rosetta.knappsack.0-1

TUPLE: item
name weight value ;

CONSTANT: items {
T{ item f "map" 9 150 }
T{ item f "compass" 13 35 }
T{ item f "water" 153 200 }
T{ item f "sandwich" 50 160 }
T{ item f "glucose" 15 60 }
T{ item f "tin" 68 45 }
T{ item f "banana" 27 60 }
T{ item f "apple" 39 40 }
T{ item f "cheese" 23 30 }
T{ item f "beer" 52 10 }
T{ item f "suntan cream" 11 70 }
T{ item f "camera" 32 30 }
T{ item f "t-shirt" 24 15 }
T{ item f "trousers" 48 10 }
T{ item f "umbrella" 73 40 }
T{ item f "waterproof trousers" 42 70 }
T{ item f "waterproof overclothes" 43 75 }
T{ item f "note-case" 22 80 }
T{ item f "sunglasses" 7 20 }
T{ item f "towel" 18 12 }
T{ item f "socks" 4 50 }
T{ item f "book" 30 10 }
}

CONSTANT: limit 400

: make-table ( -- table )
items length 1 + [ limit 1 + 0 <array> ] replicate ;

:: iterate ( item-no table -- )
item-no table nth :> prev
item-no 1 + table nth :> curr
item-no items nth :> item
limit [1,b] [| weight |
weight prev nth
weight item weight>> - dup 0 >=
[ prev nth item value>> + max ]
[ drop ] if
weight curr set-nth
] each ;

: fill-table ( table -- )
[ items length iota ] dip
'[ _ iterate ] each ;

:: extract-packed-items ( table -- items )
[
limit :> weight!
items length iota <reversed> [| item-no |
item-no table nth :> prev
item-no 1 + table nth :> curr
weight [ curr nth ] [ prev nth ] bi =
[
item-no items nth
[ name>> , ] [ weight>> weight swap - weight! ] bi
] unless
] each
] { } make ;

: solve-knappsack ( -- items value )
make-table [ fill-table ]
[ extract-packed-items ] [ last last ] tri ;

: main ( -- )
solve-knappsack
"Total value: " write number>string print
"Items packed: " print
natural-sort
[ "   " write print ] each ;
Total value: 1030
Items packed:
banana
compass
glucose
map
note-case
sandwich
socks
sunglasses
suntan cream
water
waterproof overclothes
waterproof trousers

## Forth

\ Rosetta Code Knapp-sack 0-1 problem.  Tested under GForth 0.7.3.
\ 22 items. On current processors a set fits nicely in one CELL (32 or 64 bits).
\ Brute force approach: for every possible set of 22 items,
\ check for admissible solution then for optimal set.

: offs HERE over - ;
400 VALUE WLIMIT
0 VALUE ITEM
0 VALUE VAL
0 VALUE /ITEM
0 VALUE ITEMS#
Create Sack
HERE
9 ,                     offs TO VAL
150 ,                   offs TO ITEM
s" map            " s,  offs TO /ITEM
DROP
13 ,  35 , s" compass        " s,
153 , 200 , s" water          " s,
50 , 160 , s" sandwich       " s,
15 ,  60 , s" glucose        " s,
68 ,  45 , s" tin            " s,
27 ,  60 , s" banana         " s,
39 ,  40 , s" apple          " s,
23 ,  30 , s" cheese         " s,
52 ,  10 , s" beer           " s,
11 ,  70 , s" suntan cream   " s,
32 ,  30 , s" camera         " s,
24 ,  15 , s" T-shirt        " s,
48 ,  10 , s" trousers       " s,
73 ,  40 , s" umbrella       " s,
42 ,  70 , s" wp trousers    " s,
43 ,  75 , s" wp overclothes " s,
22 ,  80 , s" note-case      " s,
7 ,  20 , s" sunglasses     " s,
18 ,  12 , s" towel          " s,
4 ,  50 , s" socks          " s,
30 ,  10 , s" book           " s,
HERE VALUE END-SACK
VARIABLE Sol            \ Solution  Set
VARIABLE Vmax           \ Temporary Maximum Value
VARIABLE Sum            \ Temporary Sum (for speed-up)
: ]sum          ( Rtime: set -- sum  ;Ctime: hilimit.a start.a -- )
\ Loop unwinding & precomputing addresses
]
]] Sum OFF [[
DO              ]] dup [[  1  ]] LITERAL AND IF [[  I  ]] LITERAL @ Sum +! THEN 2/ [[
/ITEM +LOOP     ]] drop Sum @ [[
; IMMEDIATE
: solve         ( -- )
Vmax OFF
[ 1 END-SACK Sack - /ITEM / lshift 1- ]L 0
DO
I [ END-SACK Sack ]sum ( by weight ) WLIMIT <
IF
I [ END-SACK VAL + Sack VAL + ]sum ( by value )
dup Vmax @ >
IF  Vmax ! I Sol !  ELSE  drop  THEN
THEN
LOOP
;
: .solution     ( -- )
Sol @ END-SACK ITEM + Sack ITEM +
DO
dup 1 AND  IF  I count type cr  THEN
2/
/ITEM +LOOP
drop
." Weight: " Sol @ [ END-SACK Sack ]sum .  ."  Value: " Sol @ [ END-SACK VAL + Sack VAL + ]sum .
;
Output:
map
compass
water
sandwich
glucose
banana
suntan cream
wp trousers
wp overclothes
note-case
sunglasses
socks
Weight: 396  Value: 1030

## FreeBASIC

Translation of: XPL0
#define Tabu = Chr(9)
Dim As Integer i, A, P, V, N
Dim As Integer MejorArticulo, MejorValor = 0
Type Knapsack
articulo As String*22
peso As Integer
valor As Integer
End Type
Dim item(1 To 22) As Knapsack => { _
("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)}

For i = 1 To (1 Shl 22)-1
A = i : P = 0 : V = 0 : N = 1
While A
If A And 1 Then
P += item(N).peso
V += item(N).valor
End If
A Shr= 1
N += 1
Wend
If V > MejorValor  And  P <= 400 Then
MejorValor = V
MejorArticulo = i
End If
Next

A = MejorArticulo : P = 0 : V = 0 : N = 1
While A
If A And 1 Then
Print "  "; item(N).articulo; Tabu;
Print item(N).peso; Tabu; item(N).valor
P += item(N).peso
V += item(N).valor
End If
A Shr= 1 : N += 1
Wend
Print "Totals:"; Spc(25); P; Tabu; V
Sleep
Output:
Same as XLP0 entry.

## Free Pascal

Dynamic programming solution(tested with FPC 3.2.2).

program Knapsack01;
{\$mode objfpc}{\$j-}
uses
Math;

type
TItem = record
Name: string;
Weight, Value: Integer;
end;

const
NUM_ITEMS = 22;
ITEMS: array[0..NUM_ITEMS-1] of TItem = (
(Name: 'map';                    Weight:   9; Value: 150),
(Name: 'compass';                Weight:  13; Value:  35),
(Name: 'water';                  Weight: 153; Value: 200),
(Name: 'sandwich';               Weight:  50; Value: 160),
(Name: 'glucose';                Weight:  15; Value:  60),
(Name: 'tin';                    Weight:  68; Value:  45),
(Name: 'banana';                 Weight:  27; Value:  60),
(Name: 'apple';                  Weight:  39; Value:  40),
(Name: 'cheese';                 Weight:  23; Value:  30),
(Name: 'beer';                   Weight:  52; Value:  10),
(Name: 'suntan cream';           Weight:  11; Value:  70),
(Name: 'camera';                 Weight:  32; Value:  30),
(Name: 'T-shirt';                Weight:  24; Value:  15),
(Name: 'trousers';               Weight:  48; Value:  10),
(Name: 'umbrella';               Weight:  73; Value:  40),
(Name: 'waterproof trousers';    Weight:  42; Value:  70),
(Name: 'waterproof overclothes'; Weight:  43; Value:  75),
(Name: 'note-case';              Weight:  22; Value:  80),
(Name: 'sunglasses';             Weight:   7; Value:  20),
(Name: 'towel';                  Weight:  18; Value:  12),
(Name: 'socks';                  Weight:   4; Value:  50),
(Name: 'book';                   Weight:  30; Value:  10)
);
MAX_WEIGHT = 400;

var
D: array of array of Integer;
I, W, V, MaxWeight: Integer;
begin
SetLength(D, NUM_ITEMS + 1, MAX_WEIGHT + 1);
for I := 0 to High(ITEMS) do
for W := 0 to MAX_WEIGHT do
if ITEMS[I].Weight > W then
D[I+1, W] := D[I, W]
else
D[I+1, W] := Max(D[I, W], D[I, W - ITEMS[I].Weight] + ITEMS[I].Value);

W := MAX_WEIGHT;
V := D[NUM_ITEMS, W];
MaxWeight := 0;
WriteLn('bagged:');
for I := High(ITEMS) downto 0 do
if (D[I+1, W] = V)and(D[I, W - ITEMS[I].Weight] = V - ITEMS[I].Value)then begin
WriteLn('  ', ITEMS[I].Name);
Inc(MaxWeight, ITEMS[I].Weight);
Dec(W, ITEMS[I].Weight);
Dec(V, ITEMS[I].Value);
end;
WriteLn('value  = ', D[NUM_ITEMS, MAX_WEIGHT]);
WriteLn('weight = ', MaxWeight);
end.
Output:
bagged:
socks
sunglasses
note-case
waterproof overclothes
waterproof trousers
suntan cream
banana
glucose
sandwich
water
compass
map
value  = 1030
weight = 396

## FutureBasic

window 1, @"Knapsack Problem", (0,0,480,270)

_maxWeight = 400

void local fn FillKnapsack
long              totalWeight = 0, totalValue = 0, itemWeight, unusedWeight
CFDictionaryRef   item, extraItem = NULL
SortDescriptorRef sd
CFMutableArrayRef packedItems

CFArrayRef items = @[
@{@"item":@"map",                    @"weight":@9,   @"value":@150},
@{@"item":@"compass",                @"weight":@13,  @"value":@35 },
@{@"item":@"water",                  @"weight":@153, @"value":@200},
@{@"item":@"sandwich",               @"weight":@50,  @"value":@160},
@{@"item":@"glucose",                @"weight":@15,  @"value":@60 },
@{@"item":@"tin",                    @"weight":@68,  @"value":@45 },
@{@"item":@"banana",                 @"weight":@27,  @"value":@60 },
@{@"item":@"apple",                  @"weight":@39,  @"value":@40 },
@{@"item":@"cheese",                 @"weight":@23,  @"value":@30 },
@{@"item":@"beer",                   @"weight":@52,  @"value":@10 },
@{@"item":@"suntan cream",           @"weight":@11,  @"value":@70 },
@{@"item":@"camera",                 @"weight":@32,  @"value":@30 },
@{@"item":@"T-shirt",                @"weight":@24,  @"value":@15 },
@{@"item":@"trousers",               @"weight":@48,  @"value":@10 },
@{@"item":@"umbrella",               @"weight":@73,  @"value":@40 },
@{@"item":@"waterproof trousers",    @"weight":@42,  @"value":@70 },
@{@"item":@"waterproof overclothes", @"weight":@43,  @"value":@75 },
@{@"item":@"note-case",              @"weight":@22,  @"value":@80 },
@{@"item":@"sunglasses",             @"weight":@7,   @"value":@20 },
@{@"item":@"towel",                  @"weight":@18,  @"value":@12 },
@{@"item":@"socks",                  @"weight":@4,   @"value":@50 },
@{@"item":@"book",                   @"weight":@30,  @"value":@10 }
]

sd = fn SortDescriptorWithKey( @"value", NO )
items = fn ArraySortedArrayUsingDescriptors( items, @[sd] )
packedItems = fn MutableArrayWithCapacity(0)
for item in items
itemWeight = fn NumberIntegerValue(item[@"weight"])
if ( totalWeight + itemWeight <= _maxWeight )
totalWeight += itemWeight
totalValue += fn NumberIntegerValue(item[@"value"])
end if
next

text @"Menlo-Bold",,, fn ColorWithRGB(1.0,0.0,1.0,0.25),, 170
print @"Item",@"Weight",@"Value"
text @"Menlo",,, fn ColorClear
for item in packedItems
printf @"%@\t%6ld\t%5ld",item[@"item"],fn NumberIntegerValue(item[@"weight"]),fn NumberIntegerValue(item[@"value"])
next
text ,,, fn ColorWithRGB(1.0,0.0,1.0,0.25)
printf @"knapsack\t%6ld\t%5ld",totalWeight,totalValue

text
print

unusedWeight = _maxWeight - totalWeight

for item in items
if ( fn NumberIntegerValue(item[@"weight"]) <= unusedWeight )
extraItem = item : break
end if
next

if ( extraItem ) then printf @"There's just enough room for extra %@!", extraItem[@"item"]
end fn

fn FillKnapsack

HandleEvents
Output:
Item                    Weight              Value
water                      153                200
sandwich                    50                160
map                          9                150
note-case                   22                 80
waterproof overclothes      43                 75
suntan cream                11                 70
waterproof trousers         42                 70
glucose                     15                 60
banana                      27                 60
socks                        4                 50
compass                     13                 35
sunglasses                   7                 20

knapsack                   396               1030

There's just enough room for extra socks!

## Go

From WP, "0-1 knapsack problem" under The Knapsack Problem, although the solution here simply follows the recursive defintion and doesn't even use the array optimization.

package main

import "fmt"

type item struct {
string
w, v int
}

var wants = []item{
{"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},
}

const maxWt = 400

func main() {
items, w, v := m(len(wants)-1, maxWt)
fmt.Println(items)
fmt.Println("weight:", w)
fmt.Println("value:", v)
}

func m(i, w int) ([]string, int, int) {
if i < 0 || w == 0 {
return nil, 0, 0
} else if wants[i].w > w {
return m(i-1, w)
}
i0, w0, v0 := m(i-1, w)
i1, w1, v1 := m(i-1, w-wants[i].w)
v1 += wants[i].v
if v1 > v0 {
return append(i1, wants[i].string), w1 + wants[i].w, v1
}
return i0, w0, v0
}
Output:
[map compass water sandwich glucose banana suntan cream waterproof trousers waterproof overclothes note-case sunglasses socks]
weight: 396
value: 1030

Alternative test case

Data for which a greedy algorithm might give an incorrect result:

var wants = []item{
{"sunscreen", 15, 2},
{"GPS", 25, 2},
{"beer", 35, 3},
}

const maxWt = 40
Output:
[sunscreen GPS]
weight: 40
value: 4

## Groovy

Solution #1: brute force

def totalWeight = { list -> list*.weight.sum() }
def totalValue = { list -> list*.value.sum() }

def knapsack01bf = { possibleItems ->
possibleItems.subsequences().findAll{ ss ->
def w = totalWeight(ss)
350 < w && w < 401
}.max(totalValue)
}

Solution #2: dynamic programming

def knapsack01dp = { possibleItems ->
def n = possibleItems.size()
def m = (0..n).collect{ i -> (0..400).collect{ w -> []} }
(1..400).each { w ->
(1..n).each { i ->
def wi = possibleItems[i-1].weight
m[i][w] = wi > w ? m[i-1][w] : ([m[i-1][w], m[i-1][w-wi] + [possibleItems[i-1]]].max(totalValue))
}
}
m[n][400]
}

Test:

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

[knapsack01bf, knapsack01dp].each { knapsack01 ->
def start = System.currentTimeMillis()
def packingList = knapsack01(items)
def elapsed = System.currentTimeMillis() - start

println "\n\n\nElapsed Time: \${elapsed/1000.0} s"
println "Total Weight: \${totalWeight(packingList)}"
println " Total Value: \${totalValue(packingList)}"
packingList.each {
printf ("  item: %-25s  weight:%4d  value:%4d\n", it.name, it.weight, it.value)
}
}
Output:
Elapsed Time: 132.267 s
Total Weight: 396
Total Value: 1030
item: map                        weight:   9  value: 150
item: compass                    weight:  13  value:  35
item: water                      weight: 153  value: 200
item: sandwich                   weight:  50  value: 160
item: glucose                    weight:  15  value:  60
item: banana                     weight:  27  value:  60
item: suntan cream               weight:  11  value:  70
item: waterproof trousers        weight:  42  value:  70
item: waterproof overclothes     weight:  43  value:  75
item: note-case                  weight:  22  value:  80
item: sunglasses                 weight:   7  value:  20
item: socks                      weight:   4  value:  50

Elapsed Time: 0.27 s
Total Weight: 396
Total Value: 1030
item: map                        weight:   9  value: 150
item: compass                    weight:  13  value:  35
item: water                      weight: 153  value: 200
item: sandwich                   weight:  50  value: 160
item: glucose                    weight:  15  value:  60
item: banana                     weight:  27  value:  60
item: suntan cream               weight:  11  value:  70
item: waterproof trousers        weight:  42  value:  70
item: waterproof overclothes     weight:  43  value:  75
item: note-case                  weight:  22  value:  80
item: sunglasses                 weight:   7  value:  20
item: socks                      weight:   4  value:  50

Brute force:

inv = [("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), ("cream",11,70), ("camera",32,30),
("tshirt",24,15), ("trousers",48,10), ("umbrella",73,40), ("trousers",42,70),
("overclothes",43,75), ("notecase",22,80), ("sunglasses",7,20), ("towel",18,12),
("socks",4,50), ("book",30,10)]

-- get all combos of items under total weight sum; returns value sum and list
combs [] _ = [ (0, []) ]
combs ((name,w,v):rest) cap = combs rest cap ++
if w > cap then [] else map (prepend (name,w,v)) (combs rest (cap - w))
where prepend (name,w,v) (v2, lst) = (v2 + v, (name,w,v):lst)

main = do
putStr "Total value: "; print value
mapM_ print items
where (value, items) = maximum \$ combs inv 400
Output:
Total value: 1030
("map",9,150)
("compass",13,35)
("water",153,200)
("sandwich",50,160)
("glucose",15,60)
("banana",27,60)
("cream",11,70)
("trousers",42,70)
("overclothes",43,75)
("notecase",22,80)
("sunglasses",7,20)
("socks",4,50)

Much faster brute force solution that computes the maximum before prepending, saving most of the prepends:

inv = [("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), ("cream",11,70), ("camera",32,30),
("tshirt",24,15), ("trousers",48,10), ("umbrella",73,40), ("trousers",42,70),
("overclothes",43,75), ("notecase",22,80), ("sunglasses",7,20), ("towel",18,12),
("socks",4,50), ("book",30,10)]

combs [] _ = (0, [])
combs ((name,w,v):rest) cap
| w <= cap  = max skipthis \$ prepend (name,w,v) (combs rest (cap - w))
| otherwise = skipthis
where	prepend (name,w,v) (v2, lst) = (v2 + v, (name,w,v):lst)
skipthis = combs rest cap

main = do print \$ combs inv 400
Output:
(1030,[("map",9,150),("compass",13,35),("water",153,200),("sandwich",50,160),("glucose",15,60),("banana",27,60),("cream",11,70),("trousers",42,70),("overclothes",43,75),("notecase",22,80),("sunglasses",7,20),("socks",4,50)])

Dynamic programming with a list for caching (this can be adapted to bounded problem easily):

inv = [("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), ("cream",11,70), ("camera",32,30),
("tshirt",24,15), ("trousers",48,10), ("umbrella",73,40),
("waterproof trousers",42,70), ("overclothes",43,75), ("notecase",22,80),
("sunglasses",7,20), ("towel",18,12), ("socks",4,50), ("book",30,10)]

knapsack = foldr addItem (repeat (0,[])) where
addItem (name,w,v) list = left ++ zipWith max right newlist where
newlist = map (\(val, names)->(val + v, name:names)) list
(left,right) = splitAt w list

main = print \$ (knapsack inv) !! 400
Output:
(1030,["map","compass","water","sandwich","glucose","banana","cream","waterproof trousers","overclothes","notecase","sunglasses","socks"])

## Icon and Unicon

Translation from Wikipedia pseudo-code. Memoization can be enabled with a command line argument that causes the procedure definitions to be swapped which effectively hooks the procedure.

global wants                    # items wanted for knapsack

procedure main(A) # kanpsack 0-1
if !A == ("--trace"|"-t") then &trace := -1     # trace everything (debug)
if !A == ("--memoize"|"-m") then m :=: Memo_m   # hook (swap) procedure

printf("Knapsack-0-1: with maximum weight allowed=%d.\n",maxw  := 400)
showwanted(wants := get_wants())
showcontents(bag := m(*wants,maxw))
printf("Performance: time=%d ms collections=%d\n",&time,&collections)
end

record packing(items,weight,value)

procedure Memo_m(i,w)           #: Hook procedure to memoize the knapsack
static memoT
initial memoT := table()
return \memoT[k := i||","||w] | ( memoT[k] := Memo_m(i,w) )
end

procedure m(i,w)                #: Solve the Knapsack 0-1 as per Wikipedia
static nil
initial nil := packing([],0,0)
if 0 = (i | w) then
return nil
else if wants[i].weight > w then
return m(i-1, w)
else {
x0 := m(i-1,w)
x1 := m(i-1,w-wants[i].weight)
if ( x1.value + wants[i].value) > x0.value then
return packing(x1.items ||| wants[i].items,
x1.weight + wants[i].weight,
x1.value + wants[i].value)
else
return x0
}
end

procedure showwanted(wants)     #: show the list of wanted items
every (tw := 0) +:= (!wants).weight
printf("Packing list has total weight=%d and includes %d items [",tw,*wants)
every printf(" %s",!(!wants).items|"]\n")
end

procedure showcontents(bag)     #: show the list of the packed bag
printf("The bag weighs=%d holding %d items [",bag.weight,*bag.items)
every printf(" %s",!bag.items|"]\n")
end

procedure get_wants()           #: setup list of wanted items
return  [ packing(["map"], 9, 150),
packing(["compass"], 13, 35),
packing(["water"], 153, 200),
packing(["sandwich"], 50, 160),
packing(["glucose"], 15, 60),
packing(["tin"], 68, 45),
packing(["banana"], 27, 60),
packing(["apple"], 39, 40),
packing(["cheese"], 23, 30),
packing(["beer"], 52, 10),
packing(["suntan cream"], 11, 70),
packing(["camera"], 32, 30),
packing(["T-shirt"], 24, 15),
packing(["trousers"], 48, 10),
packing(["umbrella"], 73, 40),
packing(["waterproof trousers"], 42, 70),
packing(["waterproof overclothes"], 43, 75),
packing(["note-case"], 22, 80),
packing(["sunglasses"], 7, 20),
packing(["towel"], 18, 12),
packing(["socks"], 4, 50),
packing(["book"], 30, 10) ]
end
Output:
Knapsack-0-1: with maximum weight allowed=400.
Packing list has total weight=803 and includes 22 items [ map compass water sandwich glucose tin banana apple cheese beer suntan cream camera T-shirt trousers umbrella waterproof trousers waterproof overclothes note-case sunglasses towel socks book ]
The bag weighs=396 holding 12 items [ map compass water sandwich glucose banana suntan cream waterproof trousers waterproof overclothes note-case sunglasses socks ]
Performance: time=37 ms collections=0

The above shows memoized performance. Un-memoized results on the same PC took time=9728 ms collections=4.

## J

Static solution:

'names values'=:|:".;._2]0 :0
'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
'tshirt';                   24          15
'trousers';                 48          10
'umbrella';                 73          40
'waterproof trousers';      42          70
'waterproof overclothes';   43          75
'notecase';                 22          80
'sunglasses';                7          20
'towel';                    18          12
'socks';                     4          50
'book';                     30          10
)

X=: +/ .*"1
plausible=: (] (] #~ 400 >: X) #:@i.@(2&^)@#)@:({."1)
best=: (plausible ([ {~  [ (i. >./)@:X {:"1@]) ]) values

+/best#values  NB. total weight and value
396 1030
best#names
map
compass
water
sandwich
glucose
banana
suntan cream
waterproof trousers
waterproof overclothes
notecase
sunglasses
socks

Alternative test case

'names values'=:|:".;._2]0 :0
'sunscreen'; 15 2
'GPS'; 25 2
'beer'; 35 3
)

X=: +/ .*"1
plausible=: (] (] #~ 40 >: X) #:@i.@(2&^)@#)@:({."1)
best=: (plausible ([ {~  [ (i. >./)@:X {:"1@]) ]) values

Illustration:

+/best#values
40 4
best#names
sunscreen
GPS

## Java

General dynamic solution after wikipedia.

package hu.pj.alg.test;

import hu.pj.alg.ZeroOneKnapsack;
import hu.pj.obj.Item;
import java.util.*;
import java.text.*;

public class ZeroOneKnapsackForTourists {

public ZeroOneKnapsackForTourists() {
ZeroOneKnapsack zok = new ZeroOneKnapsack(400); // 400 dkg = 400 dag = 4 kg

// making the list of items that you want to bring

// calculate the solution:
List<Item> itemList = zok.calcSolution();

// write out the solution in the standard output
if (zok.isCalculated()) {
NumberFormat nf  = NumberFormat.getInstance();

System.out.println(
"Maximal weight           = " +
nf.format(zok.getMaxWeight() / 100.0) + " kg"
);
System.out.println(
"Total weight of solution = " +
nf.format(zok.getSolutionWeight() / 100.0) + " kg"
);
System.out.println(
"Total value              = " +
zok.getProfit()
);
System.out.println();
System.out.println(
"You can carry the following materials " +
"in the knapsack:"
);
for (Item item : itemList) {
if (item.getInKnapsack() == 1) {
System.out.format(
"%1\$-23s %2\$-3s %3\$-5s %4\$-15s \n",
item.getName(),
item.getWeight(), "dag  ",
"(value = " + item.getValue() + ")"
);
}
}
} else {
System.out.println(
"The problem is not solved. " +
"Maybe you gave wrong data."
);
}

}

public static void main(String[] args) {
new ZeroOneKnapsackForTourists();
}

} // class
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>();

for (int j = 0; j <= maxWeight; j++)
for (int i = 1; i <= n; i++) {
List<Integer> prev = curr;
for (int j = 0; j <= maxWeight; j++) {
if (j > 0) {
int wH = itemList.get(i-1).getWeight();
(wH > j)
?
prev.get(j)
:
Math.max(
prev.get(j),
itemList.get(i-1).getValue() + prev.get(j-wH)
)
);
} else {
}
} // 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);
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
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
Output:
Maximal weight           = 4 kg
Total weight of solution = 3,96 kg
Total value              = 1030

You can carry te following materials in the knapsack:
map                     9   dag   (value = 150)
compass                 13  dag   (value = 35)
water                   153 dag   (value = 200)
sandwich                50  dag   (value = 160)
glucose                 15  dag   (value = 60)
banana                  27  dag   (value = 60)
suntan cream            11  dag   (value = 70)
waterproof trousers     42  dag   (value = 70)
waterproof overclothes  43  dag   (value = 75)
note-case               22  dag   (value = 80)
sunglasses              7   dag   (value = 20)
socks                   4   dag   (value = 50)

## JavaScript

Also available at gist.

/*global portviz:false, _:false */
/*
* 0-1 knapsack solution, recursive, memoized, approximate.
*
* credits:
*
* the Go implementation here:
*   http://rosettacode.org/mw/index.php?title=Knapsack_problem/0-1
*
* approximation details here:
*   http://math.mit.edu/~goemans/18434S06/knapsack-katherine.pdf
*/
portviz.knapsack = {};
(function() {
this.combiner = function(items, weightfn, valuefn) {
// approximation guarantees result >= (1-e) * optimal
var _epsilon = 0.01;
var _p = _.max(_.map(items,valuefn));
var _k = _epsilon * _p / items.length;

var _memo = (function(){
var _mem = {};
var _key = function(i, w) {
return i + '::' + w;
};
return {
get: function(i, w) {
return _mem[_key(i,w)];
},
put: function(i, w, r) {
_mem[_key(i,w)]=r;
return r;
}
};
})();

var _m = function(i, w) {

i = Math.round(i);
w = Math.round(w);

if (i < 0 || w === 0) {
// empty base case
return {items: [], totalWeight: 0, totalValue: 0};
}

var mm = _memo.get(i,w);
if (!_.isUndefined(mm)) {
return mm;
}

var item = items[i];
if (weightfn(item) > w) {
//item does not fit, try the next item
return _memo.put(i, w, _m(i-1, w));
}
// this item could fit.
// are we better off excluding it?
var excluded = _m(i-1, w);
// or including it?
var included = _m(i-1, w - weightfn(item));
if (included.totalValue + Math.floor(valuefn(item)/_k) > excluded.totalValue) {
// better off including it
// make a copy of the list
var i1 = included.items.slice();
i1.push(item);
return _memo.put(i, w,
{items: i1,
totalWeight: included.totalWeight + weightfn(item),
totalValue: included.totalValue + Math.floor(valuefn(item)/_k)});
}
//better off excluding it
return _memo.put(i,w, excluded);
};
return {
/* one point */
one: function(maxweight) {
var scaled = _m(items.length - 1, maxweight);
return {
items: scaled.items,
totalWeight: scaled.totalWeight,
totalValue: scaled.totalValue * _k
};
},
/* the entire EF */
ef: function(maxweight, step) {
return _.map(_.range(0, maxweight+1, step), function(weight) {
var scaled = _m(items.length - 1, weight);
return {
items: scaled.items,
totalWeight: scaled.totalWeight,
totalValue: scaled.totalValue * _k
};
});
}
};
};
}).apply(portviz.knapsack);

/*global portviz:false, _:false */
/*
* after rosettacode.org/mw/index.php?title=Knapsack_problem/0-1
*/
var allwants = [
{name:"map", weight:9, value: 150},
{name:"compass", weight:13, value: 35},
{name:"water", weight:153, value: 200},
{name:"sandwich", weight: 50, value: 160},
{name:"glucose", weight:15, value: 60},
{name:"tin", weight:68, value: 45},
{name:"banana", weight:27, value: 60},
{name:"apple", weight:39, value: 40},
{name:"cheese", weight:23, value: 30},
{name:"beer", weight:52, value: 10},
{name:"suntan cream", weight:11, value: 70},
{name:"camera", weight:32, value: 30},
{name:"T-shirt", weight:24, value: 15},
{name:"trousers", weight:48, value: 10},
{name:"umbrella", weight:73, value: 40},
{name:"waterproof trousers", weight:42, value: 70},
{name:"waterproof overclothes", weight:43, value: 75},
{name:"note-case", weight:22, value: 80},
{name:"sunglasses", weight:7, value: 20},
{name:"towel", weight:18, value: 12},
{name:"socks", weight:4, value: 50},
{name:"book", weight:30, value: 10}
];

var near = function(actual, expected, tolerance) {
if (expected === 0 && actual === 0) return true;
if (expected === 0) {
return Math.abs(expected - actual) / actual < tolerance;
}
return Math.abs(expected - actual) / expected < tolerance;
};

test("one knapsack", function() {
var combiner =
portviz.knapsack.combiner(allwants,
function(x){return x.weight;},
function(x){return x.value;});
var oneport = combiner.one(400);
ok(near(oneport.totalValue, 1030, 0.01), "correct total value");
ok(near(oneport.totalValue, 1030, 0.01), "correct total value");
equal(oneport.totalWeight, 396, "correct total weight");
});

test("frontier", function() {
var combiner =
portviz.knapsack.combiner(allwants,
function(x){return x.weight;},
function(x){return x.value;});
var ef = combiner.ef(400, 1);
equal(ef.length, 401, "401 because it includes the endpoints");
ef = combiner.ef(400, 40);
equal(ef.length, 11, "11 because it includes the endpoints");
var expectedTotalValue = [
0,
330,
445,
590,
685,
755,
810,
860,
902,
960,
1030
] ;
_.each(ef, function(element, index) {
// 15% error!  bleah!
ok(near(element.totalValue, expectedTotalValue[index], 0.15),
'actual ' + element.totalValue + ' expected ' + expectedTotalValue[index]);
});
deepEqual(_.pluck(ef, 'totalWeight'), [
0,
39,
74,
118,
158,
200,
236,
266,
316,
354,
396
]);
deepEqual(_.map(ef, function(x){return x.items.length;}), [
0,
4,
6,
7,
9,
10,
10,
12,
14,
11,
12
]);
});

## jq

Works with: jq version 1.4

"dynamic_knapsack(W)" implements a dynamic programming algorithm based on computing m[i,W] as the maximum value that can be attained with weight no greater than W using the first i items (with i = 0 corresponding to no items). Here, m[i,W] is set to [V, ary] where ary is an array of the names of the accepted items.

# Input should be the array of objects giving name, weight and value.
# Because of the way addition is defined on null and because of the
# way setpath works, there is no need to initialize the matrix m in
# detail.
def dynamic_knapsack(W):
. as \$objects
| length as \$n
| reduce range(1; \$n+1) as \$i                           # i is the number of items
# state: m[i][j] is an array of [value, array_of_object_names]
(null;                           # see above remark about initialization of m
\$objects[\$i-1] as \$o
| reduce range(0; W+1) as \$j
( .;
if \$o.weight <= \$j then
.[\$i-1][\$j][0] as \$v1                               # option 1: do not add this object
| (.[\$i-1][\$j - \$o.weight][0] + \$o.value) as \$v2    # option 2: add it
| (if \$v1 > \$v2 then
[\$v1, .[\$i-1][\$j][1]]                       # do not add this object
else [\$v2, .[\$i-1][\$j - \$o.weight][1]+[\$o.name]] # add it
end) as \$mx
| .[\$i][\$j] = \$mx
else
.[\$i][\$j] = .[\$i-1][\$j]
end))
| .[\$n][W];

Example:

def objects: [
{name: "map",                    "weight": 9,   "value": 150},
{name: "compass",                "weight": 13,  "value": 35},
{name: "water",                  "weight": 153, "value": 200},
{name: "sandwich",               "weight": 50,  "value": 160},
{name: "glucose",                "weight": 15,  "value": 60},
{name: "tin",                    "weight": 68,  "value": 45},
{name: "banana",                 "weight": 27,  "value": 60},
{name: "apple",                  "weight": 39,  "value": 40},
{name: "cheese",                 "weight": 23,  "value": 30},
{name: "beer",                   "weight": 52,  "value": 10},
{name: "suntancream",            "weight": 11,  "value": 70},
{name: "camera",                 "weight": 32,  "value": 30},
{name: "T-shirt",                "weight": 24,  "value": 15},
{name: "trousers",               "weight": 48,  "value": 10},
{name: "umbrella",               "weight": 73,  "value": 40},
{name: "waterproof trousers",    "weight": 42,  "value": 70},
{name: "waterproof overclothes", "weight": 43,  "value": 75},
{name: "note-case",              "weight": 22,  "value": 80},
{name: "sunglasses",             "weight": 7,   "value": 20},
{name: "towel",                  "weight": 18,  "value": 12},
{name: "socks",                  "weight": 4,   "value": 50},
{name: "book",                   "weight": 30,  "value": 10}
];

objects | dynamic_knapsack(400)[]
Output:
\$jq -M -c -n -f knapsack.jq
1030
["map","compass","water","sandwich","glucose","banana","suntancream","waterproof trousers","waterproof overclothes","note-case","sunglasses","socks"]

## Julia

This solution uses the MathProgBase package (with the Cbc solver package installed). It is the mixintprog function from this package that does the heavy lifting of this solution.

KPDSupply has one more field than is needed, quant. This field is may be useful in a solution to the bounded version of this task.

Type and Functions:

struct KPDSupply{T<:Integer}
item::String
weight::T
value::T
quant::T
end

KPDSupply{T<:Integer}(itm::AbstractString, w::T, v::T, q::T=one(T)) = KPDSupply(itm, w, v, q)
Base.show(io::IO, kdps::KPDSupply) = print(io, kdps.quant, " ", kdps.item, " (\$(kdps.weight) kg, \$(kdps.value) €)")

using MathProgBase, Cbc
function solve(gear::Vector{<:KPDSupply}, capacity::Integer)
w = getfield.(gear, :weight)
v = getfield.(gear, :value)
sol = mixintprog(-v, w', '<', capacity, :Bin, 0, 1, CbcSolver())
gear[sol.sol .≈ 1]
end

Main:

gear = [KPDSupply("map", 9, 150),
KPDSupply("compass", 13, 35),
KPDSupply("water", 153, 200),
KPDSupply("sandwich", 50, 160),
KPDSupply("glucose", 15, 60),
KPDSupply("tin", 68, 45),
KPDSupply("banana", 27, 60),
KPDSupply("apple", 39, 40),
KPDSupply("cheese", 23, 30),
KPDSupply("beer", 52, 10),
KPDSupply("suntan cream", 11, 70),
KPDSupply("camera", 32, 30),
KPDSupply("T-shirt", 24, 15),
KPDSupply("trousers", 48, 10),
KPDSupply("umbrella", 73, 40),
KPDSupply("waterproof trousers", 42, 70),
KPDSupply("waterproof overclothes", 43, 75),
KPDSupply("note-case", 22, 80),
KPDSupply("sunglasses", 7, 20),
KPDSupply("towel", 18, 12),
KPDSupply("socks", 4, 50),
KPDSupply("book", 30, 10)]

pack = solve(gear, 400)
println("The hicker should pack: \n - ", join(pack, "\n - "))
println("\nPacked weight: ", mapreduce(x -> x.weight, +, pack), " kg")
println("Packed value: ", mapreduce(x -> x.value, +, pack), " €")
Output:
The hicker should pack:
- 1 map (9 kg, 150 €)
- 1 compass (13 kg, 35 €)
- 1 water (153 kg, 200 €)
- 1 sandwich (50 kg, 160 €)
- 1 glucose (15 kg, 60 €)
- 1 banana (27 kg, 60 €)
- 1 suntan cream (11 kg, 70 €)
- 1 waterproof trousers (42 kg, 70 €)
- 1 waterproof overclothes (43 kg, 75 €)
- 1 note-case (22 kg, 80 €)
- 1 sunglasses (7 kg, 20 €)
- 1 socks (4 kg, 50 €)

Packed weight: 396 kg
Packed value: 1030 €

## Kotlin

Translation of: Go
// version 1.1.2

data class Item(val name: String, val weight: Int, val value: Int)

val wants = listOf(
Item("map", 9, 150),
Item("compass", 13, 35),
Item("water", 153, 200),
Item("sandwich", 50, 160),
Item("glucose", 15, 60),
Item("tin", 68, 45),
Item("banana", 27, 60),
Item("apple", 39, 40),
Item("cheese", 23, 30),
Item("beer", 52, 10),
Item("suntan cream", 11, 70),
Item("camera", 32, 30),
Item("T-shirt", 24, 15),
Item("trousers", 48, 10),
Item("umbrella", 73, 40),
Item("waterproof trousers", 42, 70),
Item("waterproof overclothes", 43, 75),
Item("note-case", 22, 80),
Item("sunglasses", 7, 20),
Item("towel", 18, 12),
Item("socks", 4, 50),
Item("book", 30, 10)
)

const val MAX_WEIGHT = 400

fun m(i: Int, w: Int): Triple<MutableList<Item>, Int, Int> {
val chosen = mutableListOf<Item>()
if (i < 0 || w == 0) return Triple(chosen, 0, 0)
else if (wants[i].weight > w) return m(i - 1, w)
val (l0, w0, v0) = m(i - 1, w)
var (l1, w1, v1) = m(i - 1, w - wants[i].weight)
v1 += wants[i].value
if (v1 > v0) {
return Triple(l1, w1 + wants[i].weight, v1)
}
return Triple(l0, w0, v0)
}

fun main(args: Array<String>) {
val (chosenItems, totalWeight, totalValue) = m(wants.size - 1, MAX_WEIGHT)
println("Knapsack Item Chosen    Weight Value")
println("----------------------  ------ -----")
for (item in chosenItems.sortedByDescending { it.value} )
println("----------------------  ------ -----")
println("Total \${chosenItems.size} Items Chosen     \$totalWeight   \$totalValue")
}
Output:
Knapsack Item Chosen    Weight Value
----------------------  ------ -----
water                     153    200
sandwich                   50    160
map                         9    150
note-case                  22     80
waterproof overclothes     43     75
suntan cream               11     70
waterproof trousers        42     70
glucose                    15     60
banana                     27     60
socks                       4     50
compass                    13     35
sunglasses                  7     20
----------------------  ------ -----
Total 12 Items Chosen     396   1030

## LSL

To test it yourself, rez a box on the ground, add the following as a New Script, create a notecard named "Knapsack_Problem_0_1_Data.txt" with the data shown below.

string sNOTECARD = "Knapsack_Problem_0_1_Data.txt";
integer iMAX_WEIGHT = 400;
integer iSTRIDE = 4;
list lList = [];
default {
integer iNotecardLine = 0;
state_entry() {
llGetNotecardLine(sNOTECARD, iNotecardLine);
}
dataserver(key kRequestId, string sData) {
if(sData==EOF) {
//llOwnerSay("EOF");
lList = llListSort(lList, iSTRIDE, FALSE);
integer iTotalWeight = 0;
integer iTotalValue = 0;
list lKnapsack = [];
integer x = 0;
while(x*iSTRIDE<llGetListLength(lList)) {
float fValueWeight = (float)llList2String(lList, x*iSTRIDE);
string sItem = (string)llList2String(lList, x*iSTRIDE+1);
integer iWeight = (integer)llList2String(lList, x*iSTRIDE+2);
integer iValue = (integer)llList2String(lList, x*iSTRIDE+3);
if(iTotalWeight+iWeight<iMAX_WEIGHT) {
iTotalWeight += iWeight;
iTotalValue += iValue;
lKnapsack += [sItem, iWeight, iValue, fValueWeight];
}
x++;
}
for(x=0 ; x*iSTRIDE<llGetListLength(lKnapsack) ; x++) {
llOwnerSay((string)x+": "+llList2String(lList, x*iSTRIDE+1)+", "+llList2String(lList, x*iSTRIDE+2)+", "+llList2String(lList, x*iSTRIDE+3));

}
llOwnerSay("iTotalWeight="+(string)iTotalWeight);
llOwnerSay("iTotalValue="+(string)iTotalValue);
} else {
//llOwnerSay((string)iNotecardLine+": "+sData);
if(llStringTrim(sData, STRING_TRIM)!="") {
list lParsed = llParseString2List(sData, [","], []);
string sItem = llStringTrim(llList2String(lParsed, 0), STRING_TRIM);
integer iWeight = (integer)llStringTrim(llList2String(lParsed, 1), STRING_TRIM);
integer iValue = (integer)llStringTrim(llList2String(lParsed, 2), STRING_TRIM);
float fValueWeight = (1.0*iValue)/iWeight;
lList += [fValueWeight, sItem, iWeight, iValue];
}
llGetNotecardLine(sNOTECARD, ++iNotecardLine);
}
}
}

Notecard:

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
Output:
0: map, 9, 150
1: socks, 4, 50
2: suntan cream, 11, 70
3: glucose, 15, 60
4: note-case, 22, 80
5: sandwich, 50, 160
6: sunglasses, 7, 20
7: compass, 13, 35
8: banana, 27, 60
9: waterproof overclothes, 43, 75
10: waterproof trousers, 42, 70
11: water, 153, 200
iTotalWeight=396
iTotalValue=1030

## Lua

This version is adapted from the Clojure version.

items = {
{"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},
}

local unpack = table.unpack

function m(i, w)
if i<1 or w==0 then
return 0, {}
else
local _, wi, vi = unpack(items[i])
if wi > w then
return mm(i - 1, w)
else
local vn, ln = mm(i - 1, w)
local vy, ly = mm(i - 1, w - wi)
if vy + vi > vn then
return vy + vi, { i, ly }
else
return vn, ln
end
end
end
end

local memo, mm_calls = {}, 0
function mm(i, w) -- memoization function for m
mm_calls = mm_calls + 1
local key = 10000*i + w
local result = memo[key]
if not result then
result = { m(i, w) }
memo[key] = result
end
return unpack(result)
end

local total_value, index_list = m(#items, 400)

return function()
return item
end
end

local names = {}
local total_weight = 0
for i in list_items(index_list) do
local name, weight = unpack(items[i])
table.insert(names, 1, name)
total_weight = total_weight + weight
end

local function printf(fmt, ...) print(string.format(fmt, ...)) end
printf("items to pack: %s", table.concat(names, ", "))
printf("total value: %d", total_value)
printf("total weight: %d", total_weight)

-- out of curiosity
local count = 0
for k,v in pairs(memo) do count = count + 1 end
printf("\n(memo count: %d; mm call count: %d)", count, mm_calls)
Output:
items to pack: map, compass, water, sandwich, glucose, banana, suntan cream, waterproof trousers, waterproof overclothes, note-case, sunglasses, socks
total value: 1030
total weight: 396

(memo count: 5329; mm call count: 9485)

## Maple

weights := [9,13,153,50,15,68,27,39,23,52,11,32,24,48,73,42,43,22,7,18,4,30]:
vals := [150,35,200,160,60,45,60,40,30,10,70,30,15,10,40,70,75,80,20,12,50,10]:
items := ["map","compass","water","sandwich","glucose","tin","banana","apple","cheese","beer","suntan cream","camera","T-shirt","trousers","umbrella","waterproof trousers","waterproof overclothes","note-case","sunglasses","towel","socks","book"]:
acc := Array(1..numelems(vals)+1,1..400+1,1,fill=0):
len := numelems(weights):
for i from 2 to len+1 do #number of items picked + 1
for j from 2 to 401 do #weight capacity left + 1
if weights[i-1] > j-1 then
acc[i,j] := acc[i-1, j]:
else
acc[i,j] := max(acc[i-1,j], acc[i-1, j-weights[i-1]]+vals[i-1]):
end if:
end do:
end do:
printf("Total Value is %d\n", acc[len+1, 401]):
count := 0:
i := len+1:
j := 401:
while (i>1 and j>1) do
if acc[i,j] <> acc[i-1,j] then
printf("Item: %s\n", items[i-1]):
count := count+weights[i-1]:
j := j-weights[i-1]:
i := i-1:
else
i := i-1:
end if:
end do:
printf("Total Weight is %d\n", count):
Output:
Total Value is 1030
Item: socks
Item: sunglasses
Item: note-case
Item: waterproof overclothes
Item: waterproof trousers
Item: suntan cream
Item: banana
Item: glucose
Item: sandwich
Item: water
Item: compass
Item: map
Total Weight is 396

## Mathematica/Wolfram Language

Used the

#[[Flatten@
Position[LinearProgramming[-#[[;; , 3]], -{#[[;; , 2]]}, -{400},
{0, 1} & /@ #, Integers], 1], 1]] &@
{{"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}}
Output:
{"map", "compass", "water", "sandwich", "glucose", "banana", "suntan cream", "waterproof trousers", "waterproof overclothes", "note-case", "sunglasses", "socks"}

## 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};

var take{t in Items}, binary;

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 :=
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
suntancream	  11	   70
camera		  32	   30
T-shirt	  24	   15
trousers	  48	   10
umbrella	  73	   40
w-trousers	  42	   70
w-overclothes	  43	   75
note-case	  22	   80
sunglasses	  7        20
towel		  18	   12
socks		  4        50
book		  30	   10
;

end;

The solution may be found at Knapsack problem/0-1/Mathprog. Activity=1 means take, Activity=0 means don't take.

## MAXScript

global globalItems = #()
global usedMass = 0
global neededItems = #()
global totalValue = 0
struct kn_item
(
item, weight, value
)

itemStrings = #("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")

fn sortByValue a b =
(
if a[1].value > b[1].value then return -1
else
(
if a[1].value == b[1].value then return 0
else return 1
)
)
fn chooseBestItem maximumWeight: items: =
(
local itemsCopy = deepcopy items
local possibleItems = #()
for i = 1 to itemsCopy.count do
(
if itemsCopy[i].weight <= maximumWeight do append possibleItems (#(itemsCopy[i],i))
)
qsort possibleItems sortByValue
if possibleItems.count > 0 then return possibleItems[1] else return 0
)

for i = 1 to itemStrings.count do
(
local split = filterstring itemStrings[i] "#"
local itemStruct = kn_item item:split[1] weight:(split[2] as integer) \
value:(split[3] as integer)
appendifunique globalItems itemstruct
)

while usedMass < 400 do
(
local item = chooseBestItem maximumweight:(400-usedMass) items:(globalItems)
if item != 0 then
(
deleteitem globalItems (item[2])
appendifunique neededItems item[1]
usedMass += item[1].weight
) else exit
)
for i in neededitems do
(
format "Item name: %, weight: %, value:%\n" i.item i.weight i.value
totalValue += i.value
)
format "Total mass: %, Total Value: %\n" usedMass totalValue
Output:
Item name: water, weight: 153, value:200
Item name: sandwich, weight: 50, value:160
Item name: map, weight: 9, value:150
Item name: note-case, weight: 22, value:80
Item name: waterproof overclothes, weight: 43, value:75
Item name: suntan cream, weight: 11, value:70
Item name: waterproof trousers, weight: 42, value:70
Item name: glucose, weight: 15, value:60
Item name: banana, weight: 27, value:60
Item name: socks, weight: 4, value:50
Item name: compass, weight: 13, value:35
Item name: sunglasses, weight: 7, value:20
OK
Total mass: 396, Total Value: 1030
OK

## MiniZinc

%Knapsack 0/1. Nigel Galloway: October 5th., 2020.
enum Items={map,compass,water,sandwich,glucose,tin,banana,apple,cheese,beer,suntan_cream,camera,t_shirt,trousers,umbrella,waterproof_trousers,waterproof_overclothes,note_case,sunglasses,towel,socks,book};
array[Items] of int: weight=[9,13,153,50,15,68,27,39,23,52,11,32,24,48,73,42,43,22,7,18,4,30];
array[Items] of int: value =[150,35,200,160,60,45,60,40,30,10,70,30,15,10,40,70,75,80,20,12,50,10];
int: maxWeight=400;
var int: wTaken=sum(n in take)(weight[n]);
var int: wValue=sum(n in take)(value[n]);
var set of Items: take;
constraint wTaken <= maxWeight;
solve maximize wValue;
output["Take "++show(take)++"\nTotal Weight=\(wTaken) Total Value=\(wValue)"]
Output:
Take {map, compass, water, sandwich, glucose, banana, suntan_cream, waterproof_trousers, waterproof_overclothes, note_case, sunglasses, socks}
Total Weight=396 Total Value=1030

## Nim

This solution uses the same algorithm as Go and Kotlin, with some modifications to improve performance:

– use item indexes rather than items themselves;
– rather than using sequences of item indexes, use sets of item indexes which are represented as bit sets;
– use a cache for memoization.
# Knapsack. Recursive algorithm.

import algorithm
import sequtils
import tables

# Description of an item.
type Item = tuple[name: string; weight, value: int]

# List of available items.
const Items: seq[Item] = @[("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)
]

type

# Item numbers (used rather than items themselves).
Number = range[0..Items.high]

# Chosen items and their total value.
Choice = tuple[nums: set[Number]; weight, value: int]

# Cache used to speed up the search.
var cache: Table[tuple[num, weight: int], Choice]

#---------------------------------------------------------------------------------------------------

proc select(num, weightLimit: int): Choice =
## Find the best choice starting from item at index "num".

if num < 0 or weightLimit == 0:
return

if (num, weightLimit) in cache:
return cache[(num, weightLimit)]

let weight = Items[num].weight
if weight > weightLimit:
return select(num - 1, weightLimit)

# Try by leaving this item and selecting among remaining items.
result = select(num - 1, weightLimit)

# Try by taking this item and completing with some remaining items.
var result1 = select(num - 1, weightLimit - weight)
inc result1.value, Items[num].value

# Select the best choice (giving the greater value).
if result1.value > result.value:
result = (result1.nums + {num.Number}, result1.weight + weight, result1.value)

cache[(num, weightLimit)] = result

#---------------------------------------------------------------------------------------------------

let (nums, weight, value) = select(Items.high, 400)
echo "List of items:"
for num in sorted(toSeq(nums)):
echo "– ", Items[num].name
echo ""
echo "Total weight: ", weight
echo "Total value: ", value
Output:
List of items:
– map
– compass
– water
– sandwich
– glucose
– banana
– suntan cream
– waterproof trousers
– waterproof overclothes
– note-case
– sunglasses
– socks

Total weight: 396
Total value: 1030

## OCaml

A brute force solution:

let items = [
"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;
]

let comb =
List.fold_left (fun acc x -> let acc2 = List.rev_map (fun li -> x::li) acc in
List.rev_append acc acc2) [[]]

let score =
List.fold_left (fun (w_tot,v_tot) (_,w,v) -> (w + w_tot, v + v_tot)) (0,0)

let () =
let combs = comb items in
let vals = List.rev_map (fun this -> (score this, this)) combs in
let poss = List.filter (fun ((w,_), _) -> w <= 400) vals in
let _, res = List.fold_left (fun (((_,s1),_) as v1) (((_,s2),_) as v2) ->
if s2 > s1 then v2 else v1)
(List.hd poss) (List.tl poss) in
List.iter (fun (name,_,_) -> print_endline name) res;
;;

## Oz

Using constraint programming.

declare
%% maps items to pairs of Weight(hectogram) and Value
Problem = knapsack('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
)

%% 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
%% with the domain {0,1}
Solution = {Record.map Problem fun {\$ _} {FD.int 0#1} 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: "}
{ForAll
{Record.arity {Record.filter Best fun {\$ T} T == 1 end}}
System.showInfo}
{System.printInfo "\n"}
{System.showInfo "total value: "#{Value Best}}
{System.showInfo "total weight: "#{Weight Best}}
Output:
Items:
banana
compass
glucose
map
note-case
sandwich
socks
sunglasses
suntan cream
water
waterproof overclothes
waterproof trousers

total value: 1030
total weight: 396

Typically runs in less than 150 milliseconds.

## Pascal

Uses a stringlist to store the items. I used the algorithm given on Wikipedia (Knapsack problem) to find the maximum value. It is written in pseudocode that translates very easily to Pascal.

program project1;
uses
sysutils, classes, math;

const
MaxWeight = 400;
N = 22;

type
TMaxArray = array[0..N, 0..MaxWeight] of integer;

TEquipment = record
Description : string;
Weight : integer;
Value : integer;
end;

TEquipmentList = array[1..N] of TEquipment;

var
M:TMaxArray;
MaxValue, WeightLeft, i, j : integer;
S,KnapSack:TStringList;
L:string;
List:TEquipmentList;

begin
//Put all the items into an array called List
L:=
'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,suntancreme,11,70,camera,32,30,T-shirt,24,15,trousers,48,40,umbrella,73,40,' +
'waterprooftrousers,42,70,waterproofoverclothes,43,75,notecase,22,80,sunglasses,7,20,towel,18,12,' +
'socks,4,50,book,30,10';
S:=TStringList.create;
S.Commatext:=L;

For i:= 1 to N do
begin
List[i].Description:=S[3*i - 3];
List[i].Weight:=strtoint(S[3*i - 2]);
List[i].Value:=strtoint(S[3*i - 1]);
end;

//create M, a table linking the possible items for each weight
//and recording the value at that point
for j := 0 to MaxWeight do
M[0, j] := 0;

for i := 1 to N do
for j := 0 to MaxWeight do
if List[i].weight > j then
M[i, j] := M[i-1, j]
else
M[i, j] := max(M[i-1, j], M[i-1, j-List[i].weight] + List[i].value);

//get the highest total value by testing every value in table M
MaxValue := 0;
for i:=1 to N do
for j:= 0 to MaxWeight do
If M[i,j] > MaxValue then
MaxValue := m[i,j];

writeln('Highest total value : ',MaxValue);

//Work backwards through the items to find those items that go in the Knapsack (a stringlist)
KnapSack := TStringList.create;
WeightLeft := MaxWeight;
For i:= N downto 1 do
if M[i,WeightLeft] = MaxValue then
if M[i-1, WeightLeft - List[i].Weight] = MaxValue - List[i].Value then
begin
Knapsack.add(List[i].Description + ' ' + IntToStr(List[i].Weight)+ ' ' + inttostr(List[i].Value));
MaxValue := MaxValue - List[i].Value;
WeightLeft := WeightLeft - List[i].Weight;
end;

//Show the items in the knapsack
writeln('Number of items     : ',KnapSack.count);
writeln('-------------------------');
For i:= KnapSack.count-1 downto 0 do
writeln(KnapSack[i]);

KnapSack.free;
S.free;
writeln('-------------------------');
writeln('done');
end.

Output

Highest total value : 1030
Number of items     : 12
-------------------------
map 9 150
compass 13 35
water 153 200
sandwich 50 160
glucose 15 60
banana 27 60
suntancreme 11 70
waterprooftrousers 42 70
waterproofoverclothes 43 75
notecase 22 80
sunglasses 7 20
socks 4 50
-------------------------
done

## Perl

The dynamic programming solution from Wikipedia.

my \$raw = <<'TABLE';
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
suntancream		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
TABLE

my (@name, @weight, @value);
for (split "\n", \$raw) {
for ([ split /\t+/ ]) {
push @name,   \$_->[0];
push @weight, \$_->[1];
push @value,  \$_->[2];
}
}

my \$max_weight = 400;
my @p = map [map undef, 0 .. 1+\$max_weight], 0 .. \$#name;

sub optimal {
my (\$i, \$w) = @_;
return [0, []] if \$i < 0;
return \$p[\$i][\$w] if \$p[\$i][\$w];

if (\$weight[\$i] > \$w) {
\$p[\$i][\$w] = optimal(\$i - 1, \$w)
} else {
my \$x = optimal(\$i - 1, \$w);
my \$y = optimal(\$i - 1, \$w - \$weight[\$i]);

if (\$x->[0] > \$y->[0] + \$value[\$i]) {
\$p[\$i][\$w] = \$x
} else {
\$p[\$i][\$w] = [  \$y->[0] + \$value[\$i], [ @{\$y->[1]}, \$name[\$i] ]]
}
}
return \$p[\$i][\$w]
}

my \$solution = optimal(\$#name, \$max_weight);
print "\$solution->[0]: @{\$solution->[1]}\n";
Output:
1030: map compass water sandwich glucose banana suntancream waterproof trousers waterproof overclothes note-case sunglasses socks

## Phix

Trivial simplification of the Knapsack/Bounded solution. By careful ordering we can ensure we find the optimal solution first (see terminate flag).

-- demo\rosetta\knapsack0.exw
with javascript_semantics

bool terminate = false

integer attempts = 0
function knapsack(sequence res, goodies, atom points, weight, at=1, sequence chosen={})
atom {?,witem,pitem} = goodies[at]
integer n = iff(witem<=weight?1:0)
chosen &= n
points += n*pitem   -- increase value
weight -= n*witem   -- decrease weight left
if at=length(goodies) then
attempts += 1
if length(res)=0
or res<{points,weight} then
res = {points,weight,chosen}
end if
terminate = (n=1)
else
--      while n>=0 do -- full exhaustive search
while n>=0 and not terminate do -- optimised
res = knapsack(res,goodies,points,weight,at+1,deep_copy(chosen))
n -= 1
chosen[\$] = n
points -= pitem
weight += witem
end while
end if
return res
end function

function byweightedvalue(object a, b)
-- sort by weight/value
return compare(a[2]/a[3],b[2]/b[3])
-- nb other sort orders break the optimisation
end function

constant goodies = custom_sort(byweightedvalue,{
-- item                     weight 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 }})

atom t0 = time()
object {points,weight,counts} = knapsack({},goodies,0,400)
printf(1,"Value %d, weight %g [%d attempts, %3.2fs]:\n",{points,400-weight,attempts,time()-t0})
for i=1 to length(counts) do
integer c = counts[i]
if c then
printf(1,"%s\n",{goodies[i][1]})
end if
end for
Output:
Value 1030, weight 396 [9 attempts, 0.00s]:
map
socks
suntan cream
glucose
note-case
sandwich
sunglasses
compass
banana
waterproof overclothes
waterproof trousers
water

without the optimisation (ie "and not terminate" removed, full exhaustive search, further lines as above):

Value 1030, weight 396 [1216430 attempts, 0.84s]:

## PHP

#########################################################
# 0-1 Knapsack Problem Solve with memoization optimize and index returns
# \$w = weight of item
# \$v = value of item
# \$i = index
# \$aW = Available Weight
# \$m = Memo items array
# PHP Translation from Python, Memoization,
# and index return functionality added by Brian Berneker
#
#########################################################

function knapSolveFast2(\$w, \$v, \$i, \$aW, &\$m) {

global \$numcalls;
\$numcalls ++;
// echo "Called with i=\$i, aW=\$aW<br>";

// Return memo if we have one
if (isset(\$m[\$i][\$aW])) {
return array( \$m[\$i][\$aW], \$m['picked'][\$i][\$aW] );
} else {

// At end of decision branch
if (\$i == 0) {
if (\$w[\$i] <= \$aW) { // Will this item fit?
\$m[\$i][\$aW] = \$v[\$i]; // Memo this item
\$m['picked'][\$i][\$aW] = array(\$i); // and the picked item
return array(\$v[\$i],array(\$i)); // Return the value of this item and add it to the picked list

} else {
// Won't fit
\$m[\$i][\$aW] = 0; // Memo zero
\$m['picked'][\$i][\$aW] = array(); // and a blank array entry...
return array(0,array()); // Return nothing
}
}

// Not at end of decision branch..
// Get the result of the next branch (without this one)
list (\$without_i, \$without_PI) = knapSolveFast2(\$w, \$v, \$i-1, \$aW, \$m);

\$m[\$i][\$aW] = \$without_i; // Memo without including this one
\$m['picked'][\$i][\$aW] = \$without_PI; // and a blank array entry...
return array(\$without_i, \$without_PI); // and return it

} else {

// Get the result of the next branch (WITH this one picked, so available weight is reduced)
list (\$with_i,\$with_PI) = knapSolveFast2(\$w, \$v, (\$i-1), (\$aW - \$w[\$i]), \$m);
\$with_i += \$v[\$i];  // ..and add the value of this one..

// Get the greater of WITH or WITHOUT
if (\$with_i > \$without_i) {
\$res = \$with_i;
\$picked = \$with_PI;
array_push(\$picked,\$i);
} else {
\$res = \$without_i;
\$picked = \$without_PI;
}

\$m[\$i][\$aW] = \$res; // Store it in the memo
\$m['picked'][\$i][\$aW] = \$picked; // and store the picked item
return array (\$res,\$picked); // and then return it
}
}
}

\$items4 = array("map","compass","water","sandwich","glucose","tin","banana","apple","cheese","beer","suntan cream","camera","t-shirt","trousers","umbrella","waterproof trousers","waterproof overclothes","note-case","sunglasses","towel","socks","book");
\$w4 = array(9,13,153,50,15,68,27,39,23,52,11,32,24,48,73,42,43,22,7,18,4,30);
\$v4 = array(150,35,200,160,60,45,60,40,30,10,70,30,15,10,40,70,75,80,20,12,50,10);

## Initialize
\$numcalls = 0; \$m = array(); \$pickedItems = array();

## Solve
list (\$m4,\$pickedItems) = knapSolveFast2(\$w4, \$v4, sizeof(\$v4) -1, 400, \$m);

# Display Result
echo "<b>Items:</b><br>".join(", ",\$items4)."<br>";
echo "<b>Max Value Found:</b><br>\$m4 (in \$numcalls calls)<br>";
echo "<b>Array Indices:</b><br>".join(",",\$pickedItems)."<br>";

echo "<b>Chosen Items:</b><br>";
echo "<table border cellspacing=0>";
echo "<tr><td>Item</td><td>Value</td><td>Weight</td></tr>";
\$totalVal = \$totalWt = 0;
foreach(\$pickedItems as \$key) {
\$totalVal += \$v4[\$key];
\$totalWt += \$w4[\$key];
echo "<tr><td>".\$items4[\$key]."</td><td>".\$v4[\$key]."</td><td>".\$w4[\$key]."</td></tr>";
}
echo "<tr><td align=right><b>Totals</b></td><td>\$totalVal</td><td>\$totalWt</td></tr>";
echo "</table><hr>";
Output:
Items:
map, compass, water, sandwich, glucose, tin, banana, apple, cheese, beer, suntan cream, camera, t-shirt, trousers, umbrella, waterproof trousers, waterproof overclothes, note-case, sunglasses, towel, socks, book
Max Value Found:
1030 (in 8725 calls)
Array Indices:
0,1,2,3,4,6,10,15,16,17,18,20
Chosen Items:
 Item Value Weight map 150 9 compass 35 13 water 200 153 sandwich 160 50 glucose 60 15 banana 60 27 suntan cream 70 11 waterproof trousers 70 42 waterproof overclothes 75 43 note-case 80 22 sunglasses 20 7 socks 50 4 Totals 1030 396

Minimal PHP Algorithm for totals only translated from Python version as discussed in the YouTube posted video at: http://www.youtube.com/watch?v=ZKBUu_ahSR