Knapsack problem/0-1

From Rosetta Code
Jump to: navigation, search
Task
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.

Which items does the tourist carry in his knapsack so that their total weight does not exceed 400 dag [4 kg], and their total value is maximised?

[dag = decagram = 10 grams]

See also

Contents

[edit] Ada

with Ada.Text_IO;
with Ada.Strings.Unbounded;
 
procedure Knapsack_01 is
package US renames Ada.Strings.Unbounded;
 
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)));
Ada.Text_IO.Put_Line ("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

[edit] APL

    ∇ ret←NapSack;sum;b;list;total
[1] total←400
[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] list←list[⍒3⊃¨list]
[4]
[5] ret←⍬
[6]  :while 0≠⍴list
[7] ret←ret,(b←total>sum←+\2⊃¨list)/list
[8] list←1↓(~b)/list
[9] total←total-sum←¯1↑(total>sum)/sum
[10]  :end
[11] ret←⊃ret,⊂'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

[edit] 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
READ items{(item%)}.name$, items{(item%)}.weight%, items{(item%)}.ivalue%
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

[edit] 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
& ( add
= 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
|
)
| add
$ ( !ncumwght
. !ncumvalue
.  !cumsack
(!n:0&|!name)
. !tings
)
)
)
)
& add$(0.0..!things)
& out$(!maxvalue.!sack));
 
!knapsack;

Output:

  1030
. map
compass
water
sandwich
glucose
banana
suntan cream
waterproof trousers
waterproof overclothes
note-case
sunglasses
socks

[edit] C

Brute force takes 0.2 seconds-ish, so not motivated to do caching.

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
 
typedef struct {
const char * name;
int weight, value;
} item_t;
 
item_t 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},
{"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}
};
 
#define n_items (sizeof(item)/sizeof(item_t))
 
typedef struct {
uint32_t bits; /* 32 bits, can solve up to 32 items */
int value;
} solution;
 
 
void optimal(int weight, int idx, solution *s)
{
solution v1, v2;
if (idx < 0) {
s->bits = s->value = 0;
return;
}
 
if (weight < item[idx].weight) {
optimal(weight, idx - 1, s);
return;
}
 
optimal(weight, idx - 1, &v1);
optimal(weight - item[idx].weight, idx - 1, &v2);
 
v2.value += item[idx].value;
v2.bits |= (1 << idx);
 
*s = (v1.value >= v2.value) ? v1 : v2;
}
 
int main(void)
{
int i = 0, w = 0;
solution s = {0, 0};
optimal(400, n_items - 1, &s);
 
for (i = 0; i < n_items; i++) {
if (s.bits & (1 << i)) {
printf("%s\n", item[i].name);
w += item[i].weight;
}
}
printf("Total value: %d; weight: %d\n", s.value, w);
return 0;
}
Output:
map
compass
water
sandwich
glucose
banana
suntancream
waterproof trousers
waterproof overclothes
note-case
sunglasses
socks
Total value: 1030; weight: 396

[edit] C++

#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 !

[edit] 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>();
}
 
void AddItem(Item i)
{
if ((TotalWeight + i.Weight) <= MaxWeightAllowed)
items.Add(i);
}
 
public void Calculate(List<Item> items)
{
foreach (Item i in Sorte(items))
{
AddItem(i);
}
}
 
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)
{
choosenItems.Add(inputItems[i]);
}
if (i > 0)
{
if (!RecursiveF(inputItems, choosenItems, i, choosenItems.Count - 1, false, ref j))
{
choosenItems.Add(inputItems[i]);
}
}
}
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 )
{
indxToAdd = lastBound;
}
return RecursiveF(knapsackItems, choosenItems, i, lastBound - 1, true, ref indxToAdd);
}
if (indxToAdd > -1)
{
choosenItems.Insert(indxToAdd, knapsackItems[i]);
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));
Console.ReadKey();
}
}
}

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

[edit] 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

[edit] 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)))

[edit] D

[edit] 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(in Item[] items, in int limit)
pure nothrow {
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() {
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]

[edit] 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() {
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;
}
writeln("\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

[edit] Short Dynamic Programming Version

Translation of: Haskell
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() {
reduce!addItem(Pair().repeat.take(400).array, items).back.writeln;
}

Runtime about 0.04 seconds.

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

[edit] 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];
packItems.add(items[n-1]);
} else {
take[n] = false;
}
}
 
return packItems;
 
}
 
main() {
List knapsackItems = [];
knapsackItems.add(["map", 9, 150]);
knapsackItems.add(["compass", 13, 35]);
knapsackItems.add(["water", 153, 200]);
knapsackItems.add(["sandwich", 50, 160]);
knapsackItems.add(["glucose", 15, 60]);
knapsackItems.add(["tin", 68, 45]);
knapsackItems.add(["banana", 27, 60]);
knapsackItems.add(["apple", 39, 40]);
knapsackItems.add(["cheese", 23, 30]);
knapsackItems.add(["beer", 52, 10]);
knapsackItems.add(["suntan cream", 11, 70]);
knapsackItems.add(["camera", 32, 30]);
knapsackItems.add(["t-shirt", 24, 15]);
knapsackItems.add(["trousers", 48, 10]);
knapsackItems.add(["umbrella", 73, 40]);
knapsackItems.add(["waterproof trousers", 42, 70]);
knapsackItems.add(["waterproof overclothes", 43, 75]);
knapsackItems.add(["note-case", 22, 80]);
knapsackItems.add(["sunglasses", 7, 20]);
knapsackItems.add(["towel", 18, 12]);
knapsackItems.add(["socks", 4, 50]);
knapsackItems.add(["book", 30, 10]);
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

[edit] 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 |

[edit] 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
 

[edit] 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 ;
 ( scratchpad ) main
 Total value: 1030
 Items packed: 
    banana
    compass
    glucose
    map
    note-case
    sandwich
    socks
    sunglasses
    suntan cream
    water
    waterproof overclothes
    waterproof trousers

[edit] 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},
}
 
func main() {
items, w, v := m(len(wants)-1, 400)
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

[edit] 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

[edit] Haskell

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"])

[edit] 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.

link printf
 
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

printf.icn provides printf

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.

[edit] 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

Illustration of answer:

   +/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

[edit] 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
zok.add("map", 9, 150);
zok.add("compass", 13, 35);
zok.add("water", 153, 200);
zok.add("sandwich", 50, 160);
zok.add("glucose", 15, 60);
zok.add("tin", 68, 45);
zok.add("banana", 27, 60);
zok.add("apple", 39, 40);
zok.add("cheese", 23, 30);
zok.add("beer", 52, 10);
zok.add("suntan cream", 11, 70);
zok.add("camera", 32, 30);
zok.add("t-shirt", 24, 15);
zok.add("trousers", 48, 10);
zok.add("umbrella", 73, 40);
zok.add("waterproof trousers", 42, 70);
zok.add("waterproof overclothes", 43, 75);
zok.add("note-case", 22, 80);
zok.add("sunglasses", 7, 20);
zok.add("towel", 18, 12);
zok.add("socks", 4, 50);
zok.add("book", 30, 10);
 
// 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>();
 
c.add(curr);
for (int j = 0; j <= maxWeight; j++)
curr.add(0);
for (int i = 1; i <= n; i++) {
List<Integer> prev = curr;
c.add(curr = new ArrayList<Integer>());
for (int j = 0; j <= maxWeight; j++) {
if (j > 0) {
int wH = itemList.get(i-1).getWeight();
curr.add(
(wH > j)
?
prev.get(j)
:
Math.max(
prev.get(j),
itemList.get(i-1).getValue() + prev.get(j-wH)
)
);
} else {
curr.add(0);
}
} // for (j...)
} // for (i...)
profit = curr.get(maxWeight);
 
for (int i = n, j = maxWeight; i > 0 && j >= 0; i--) {
int tempI = c.get(i).get(j);
int tempI_1 = c.get(i-1).get(j);
if (
(i == 0 && tempI > 0)
||
(i > 0 && tempI != tempI_1)
)
{
Item iH = itemList.get(i-1);
int wH = iH.getWeight();
iH.setInKnapsack(1);
j -= wH;
solutionWeight += wH;
}
} // for()
calculated = true;
} // if()
return itemList;
}
 
// add an item to the item list
public void add(String name, int weight, int value) {
if (name.equals(""))
name = "" + (itemList.size() + 1);
itemList.add(new Item(name, weight, value));
setInitialStateForCalculation();
}
 
// add an item to the item list
public void add(int weight, int value) {
add("", weight, value); // the name will be "itemList.size() + 1"!
}
 
// remove an item from the item list
public void remove(String name) {
for (Iterator<Item> it = itemList.iterator(); it.hasNext(); ) {
if (name.equals(it.next().getName())) {
it.remove();
}
}
setInitialStateForCalculation();
}
 
// remove all items from the item list
public void removeAllItems() {
itemList.clear();
setInitialStateForCalculation();
}
 
public int getProfit() {
if (!calculated)
calcSolution();
return profit;
}
 
public int getSolutionWeight() {return solutionWeight;}
public boolean isCalculated() {return calculated;}
public int getMaxWeight() {return maxWeight;}
 
public void setMaxWeight(int _maxWeight) {
maxWeight = Math.max(_maxWeight, 0);
}
 
public void setItemList(List<Item> _itemList) {
if (_itemList != null) {
itemList = _itemList;
for (Item item : _itemList) {
item.checkMembers();
}
}
}
 
// set the member with name "inKnapsack" by all items:
private void setInKnapsackByAll(int inKnapsack) {
for (Item item : itemList)
if (inKnapsack > 0)
item.setInKnapsack(1);
else
item.setInKnapsack(0);
}
 
// set the data members of class in the state of starting the calculation:
protected void setInitialStateForCalculation() {
setInKnapsackByAll(0);
calculated = false;
profit = 0;
solutionWeight = 0;
}
 
} // class
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)    

[edit] 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
]);
});

[edit] 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() {
llOwnerSay("Reading '"+sNOTECARD+"'");
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:

Reading 'Knapsack_Problem_0_1_Data.txt'
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

[edit] Mathematica

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"}

[edit] 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.

[edit] 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;
;;

[edit] 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.

[edit] 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([[0, []], map undef, 0 .. $max_weight], 0 .. $#name),
[ map([0, []], 0 .. $max_weight + 1)]);
 
sub optimal {
my ($i, $w) = @_;
 
if (!defined $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 $sol = optimal($#name, $max_weight);
print "$sol->[0]: @{$sol->[1]}\n";
 
# prints:
# 1030: map compass water sandwich glucose banana suntancream waterproof trousers
# waterproof overclothes note-case sunglasses socks

[edit] Perl 6

Works with: niecza version 2012-02-17
my class KnapsackItem { has $.name; has $.weight; has $.unit; }
 
multi sub pokem ([], $, $v = 0) { $v }
multi sub pokem ([$, *@], 0, $v = 0) { $v }
multi sub pokem ([$i, *@rest], $w, $v = 0) {
my $key = "{+@rest} $w $v";
(state %cache){$key} or do {
my @skip = pokem @rest, $w, $v;
if $w >= $i.weight { # next one fits
my @put = pokem @rest, $w - $i.weight, $v + $i.unit;
return (%cache{$key} = @put, $i.name).list if @put[0] > @skip[0];
}
return (%cache{$key} = @skip).list;
}
}
 
my $MAX_WEIGHT = 400;
my @table = map -> $name, $weight, $unit {
KnapsackItem.new: :$name, :$weight, :$unit;
},
'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;
 
my ($value, @result) = pokem @table, $MAX_WEIGHT;
say "Value = $value\nTourist put in the bag:\n " ~ @result;
Output:
% perl6 knapsack1.p6 
Value = 1030
Tourist put in the bag:
  socks sunglasses note-case waterproof overclothes waterproof trousers suntan cream banana glucose sandwich water compass map

[edit] 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
#
#It works uncorrectly! For examle if $aw=4. Max value is true, but no "Array Indices" and its parameters are displayed
#
#########################################################

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,$pickedItems);
 
if ($w[$i] > $aW) { // Does it return too many?
 
$m[$i][$aW] = $without_i; // Memo without including this one
$m['picked'][$i][$aW] = array(); // and a blank array entry...
return array($without_i,array()); // 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,$pickedItems);
$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,$pickedItems);
 
# 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>";
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:
ItemValueWeight
map1509
compass3513
water200153
sandwich16050
glucose6015
banana6027
suntan cream7011
waterproof trousers7042
waterproof overclothes7543
note-case8022
sunglasses207
socks504
Totals1030396

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_ahSR4

#########################################################
# 0-1 Knapsack Problem Solve
# $w = weight of item
# $v = value of item
# $i = index
# $aW = Available Weight
# PHP Translation by Brian Berneker
#########################################################

function knapSolve($w,$v,$i,$aW) {
 
global $numcalls;
$numcalls ++;
// echo "Called with i=$i, aW=$aW<br>";
 
if ($i == 0) {
if ($w[$i] <= $aW) {
return $v[$i];
} else {
return 0;
}
}
 
$without_i = knapSolve($w, $v, $i-1, $aW);
if ($w[$i] > $aW) {
return $without_i;
} else {
$with_i = $v[$i] + knapSolve($w, $v, ($i-1), ($aW - $w[$i]));
return max($with_i, $without_i);
}
 
}
 
 
#########################################################
# 0-1 Knapsack Problem Solve (with "memo"-ization optimization)
# $w = weight of item
# $v = value of item
# $i = index
# $aW = Available Weight
# $m = 'memo' array
# PHP Translation by Brian Berneker
#########################################################

function knapSolveFast($w,$v,$i,$aW,&$m) { // Note: We use &$m because the function writes to the $m array
 
global $numcalls;
$numcalls ++;
// echo "Called with i=$i, aW=$aW<br>";
 
// Return memo if we have one
if (isset($m[$i][$aW])) {
return $m[$i][$aW];
} else {
 
if ($i == 0) {
if ($w[$i] <= $aW) {
$m[$i][$aW] = $v[$i]; // save memo
return $v[$i];
} else {
$m[$i][$aW] = 0; // save memo
return 0;
}
}
 
$without_i = knapSolveFast($w, $v, $i-1, $aW,$m);
if ($w[$i] > $aW) {
$m[$i][$aW] = $without_i; // save memo
return $without_i;
} else {
$with_i = $v[$i] + knapSolveFast($w, $v, ($i-1), ($aW - $w[$i]),$m);
$res = max($with_i, $without_i);
$m[$i][$aW] = $res; // save memo
return $res;
}
}
}
 
 
$w3 = array(1, 1, 1, 2, 2, 2, 4, 4, 4, 44, 96, 96, 96);
$v3 = array(1, 1, 1, 2, 2, 2, 4, 4, 4, 44, 96, 96, 96);
 
$numcalls = 0;
$m = array();
$m3 = knapSolveFast($w3, $v3, sizeof($v3) -1, 54,$m);
print_r($w3); echo "<br>FAST: ";
echo "<b>Max: $m3</b> ($numcalls calls)<br><br>";
 
 
$numcalls = 0;
$m = array();
$m3 = knapSolve($w3, $v3, sizeof($v3) -1, 54 );
print_r($w3); echo "<br>";
echo "<b>Max: $m3</b> ($numcalls calls)<br><br>";
Output:
Array ( [0] => 1 [1] => 1 [2] => 1 [3] => 2 [4] => 2 [5] => 2 [6] => 4 [7] => 4 [8] => 4 [9] => 44 [10] => 96 [11] => 96 [12] => 96 ) 
FAST: Max: 54 (191 calls)

Array ( [0] => 1 [1] => 1 [2] => 1 [3] => 2 [4] => 2 [5] => 2 [6] => 4 [7] => 4 [8] => 4 [9] => 44 [10] => 96 [11] => 96 [12] => 96 ) 
Max: 54 (828 calls)

[edit] PicoLisp

(de *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) )
 
# Dynamic programming solution
(de knapsack (Lst W)
(when Lst
(cache '*KnapCache (cons W Lst)
(let X (knapsack (cdr Lst) W)
(if (ge0 (- W (cadar Lst)))
(let Y (cons (car Lst) (knapsack (cdr Lst) @))
(if (> (sum caddr X) (sum caddr Y)) X Y) )
X ) ) ) ) )
 
(let K (knapsack *Items 400)
(for I K
(apply tab I (3 -24 6 6) NIL) )
(tab (27 6 6) NIL (sum cadr K) (sum caddr K)) )
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
                              396  1030

[edit] Prolog

Works with: SWI-Prolog

[edit] Using the clpfd library

Library: clpfd
:- use_module(library(clpfd)).
 
knapsack :-
L = [
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 )],
length(L, N),
length(R, N),
R ins 0..1,
maplist(arg(2), L, LW),
maplist(arg(3), L, LV),
scalar_product(LW, R, #=<, 400),
scalar_product(LV, R, #=, VM),
labeling([max(VM)], R),
scalar_product(LW, R, #=, WM),
%% affichage des résultats
compute_lenword(L, 0, Len),
sformat(A1, '~~w~~t~~~w|', [Len]),
sformat(A2, '~~t~~w~~~w|', [4]),
sformat(A3, '~~t~~w~~~w|', [5]),
print_results(A1,A2,A3, L, R, WM, VM).
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% to show the results in a good way
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
compute_lenword([], N, N).
compute_lenword([item(Name, _, _)|T], N, NF):-
atom_length(Name, L),
( L > N -> N1 = L; N1 = N),
compute_lenword(T, N1, NF).
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
print_results(A1,A2,A3, [], [], WM, WR) :-
sformat(W1, A1, [' ']),
sformat(W2, A2, [WM]),
sformat(W3, A3, [WR]),
format('~w~w~w~n', [W1,W2,W3]).
 
 
print_results(A1,A2,A3, [_H|T], [0|TR], WM, VM) :-
print_results(A1,A2,A3, T, TR, WM, VM).
 
print_results(A1, A2, A3, [item(Name, W, V)|T], [1|TR], WM, VM) :-
sformat(W1, A1, [Name]),
sformat(W2, A2, [W]),
sformat(W3, A3, [V]),
format('~w~w~w~n', [W1,W2,W3]),
print_results(A1, A2, A3, T, TR, WM, VM).
Output:
?- knapsack
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
                       396 1030

[edit] Using the simplex library

Library: simplex

Library written by Markus Triska. The problem is solved in about 3 seconds.

:- use_module(library(simplex)).
 
knapsack :-
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),
('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 )],
gen_state(S0),
length(L, N),
numlist(1, N, LN),
time(( create_constraint_N(LN, S0, S1),
maplist(create_constraint_WV, LN, L, LW, LV),
constraint(LW =< 400, S1, S2),
maximize(LV, S2, S3)
)),
compute_lenword(L, 0, Len),
sformat(A1, '~~w~~t~~~w|', [Len]),
sformat(A2, '~~t~~w~~~w|', [4]),
sformat(A3, '~~t~~w~~~w|', [5]),
print_results(S3, A1,A2,A3, L, LN, 0, 0).
 
 
create_constraint_N([], S, S).
 
create_constraint_N([HN|TN], S1, SF) :-
constraint(integral(x(HN)), S1, S2),
constraint([x(HN)] =< 1, S2, S3),
constraint([x(HN)] >= 0, S3, S4),
create_constraint_N(TN, S4, SF).
 
create_constraint_WV(N, (_, W, V), W * x(N), V * x(N)).
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
compute_lenword([], N, N).
compute_lenword([(Name, _, _)|T], N, NF):-
atom_length(Name, L),
( L > N -> N1 = L; N1 = N),
compute_lenword(T, N1, NF).
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
print_results(_S, A1, A2, A3, [], [], WM, VM) :-
sformat(W1, A1, [' ']),
sformat(W2, A2, [WM]),
sformat(W3, A3, [VM]),
format('~w~w~w~n', [W1,W2,W3]).
 
 
print_results(S, A1, A2, A3, [(Name, W, V)|T], [N|TN], W1, V1) :-
variable_value(S, x(N), X),
( X = 0 -> W1 = W2, V1 = V2
; sformat(S1, A1, [Name]),
sformat(S2, A2, [W]),
sformat(S3, A3, [V]),
format('~w~w~w~n', [S1,S2,S3]),
W2 is W1 + W,
V2 is V1 + V),
print_results(S, A1, A2, A3, T, TN, W2, V2).

[edit] PureBasic

Solution uses memoization.

Structure item
name.s
weight.i ;units are dekagrams (dag)
Value.i
EndStructure
 
Structure memo
Value.i
List picked.i()
EndStructure
 
Global itemCount = 0 ;this will be increased as needed to match count
Global Dim items.item(itemCount)
 
Procedure addItem(name.s, weight, Value)
If itemCount >= ArraySize(items())
Redim items.item(itemCount + 10)
EndIf
With items(itemCount)
\name = name
\weight = weight
\Value = Value
EndWith
itemCount + 1
EndProcedure
 
;build item list
addItem("map", 9, 150)
addItem("compass", 13, 35)
addItem("water", 153, 200)
addItem("sandwich", 50, 160)
addItem("glucose", 15, 60)
addItem("tin", 68, 45)
addItem("banana", 27, 60)
addItem("apple", 39, 40)
addItem("cheese", 23, 30)
addItem("beer", 52, 10)
addItem("suntan cream", 11, 70)
addItem("camera", 32, 30)
addItem("t-shirt", 24, 15)
addItem("trousers", 48, 10)
addItem("umbrella", 73, 40)
addItem("waterproof trousers", 42, 70)
addItem("waterproof overclothes", 43, 75)
addItem("note-case", 22, 80)
addItem("sunglasses", 7, 20)
addItem("towel", 18, 12)
addItem("socks", 4, 50)
addItem("book", 30, 10)
 
Procedure knapsackSolveFast(Array item.item(1), i, aw, Map m.memo())
Protected.memo without_i, with_i, result, *tmp, memoIndex.s = Hex((i << 16) + aw, #PB_Long)
If FindMapElement(m(), memoIndex)
ProcedureReturn @m()
Else
If i = 0
If item(0)\weight <= aw
;item fits
m(memoIndex)\Value = item(0)\Value ;memo this item's value
AddElement(m()\picked())
m()\picked() = 0 ;memo item's index also
Else
;item doesn't fit, memo a zero Value
m(memoIndex)\Value = 0
EndIf
ProcedureReturn @m()
EndIf
 
;test if a greater value results with or without item included
*tmp = knapsackSolveFast(item(), i - 1, aw, m()) ;find value without this item
CopyStructure(*tmp, @without_i, memo)
If item(i)\weight > aw
;item weighs too much, memo without including this item
m(memoIndex) = without_i
ProcedureReturn @m()
Else
*tmp = knapsackSolveFast(item(), i - 1, aw - item(i)\weight, m()) ;find value when item is included
CopyStructure(*tmp, @with_i, memo)
with_i\Value + item(i)\Value
AddElement(with_i\picked())
with_i\picked() = i ;add item to with's picked list
EndIf
 
;set the result to the larger value
If with_i\Value > without_i\Value
result = with_i
Else
result = without_i
EndIf
 
m(memoIndex) = result ;memo the result
ProcedureReturn @m()
EndIf
EndProcedure
 
Procedure.s knapsackSolve(Array item.item(1), i, aw)
Protected *result.memo, output.s, totalWeight
NewMap m.memo()
*result = knapsackSolveFast(item(), i, aw, m())
output = "Knapsack:" + #CRLF$
ForEach *result\picked()
output + LSet(item(*result\picked())\name, 24) + RSet(Str(item(*result\picked())\weight), 5) + RSet(Str(item(*result\picked())\Value), 5) + #CRLF$
totalWeight + item(*result\picked())\weight
Next
output + LSet("TOTALS:", 24) + RSet(Str(totalWeight), 5) + RSet(Str(*result\Value), 5)
ProcedureReturn output
EndProcedure
 
If OpenConsole()
#maxWeight = 400
Define *result.memo
PrintN(knapsackSolve(items(), itemCount - 1, #maxWeight))
 
Print(#CRLF$ + #CRLF$ + "Press ENTER to exit"): Input()
CloseConsole()
EndIf
Output:
Knapsack:
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

[edit] Python

[edit] Brute force algorithm

from itertools import combinations
 
def anycomb(items):
' return combinations of any length from the items '
return ( comb
for r in range(1, len(items)+1)
for comb in combinations(items, r)
)
 
def totalvalue(comb):
' Totalise a particular combination of items'
totwt = totval = 0
for item, wt, val in comb:
totwt += wt
totval += val
return (totval, -totwt) if totwt <= 400 else (0, 0)
 
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),
)
bagged = max( anycomb(items), key=totalvalue) # max val or min wt if values equal
print("Bagged the following items\n " +
'\n '.join(sorted(item for item,_,_ in bagged)))
val, wt = totalvalue(bagged)
print("for a total value of %i and a total weight of %i" % (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

[edit] Dynamic programming solution

try:
xrange
except:
xrange = range
 
def totalvalue(comb):
' Totalise a particular combination of items'
totwt = totval = 0
for item, wt, val in comb:
totwt += wt
totval += val
return (totval, -totwt) if totwt <= 400 else (0, 0)
 
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),
)
 
def knapsack01_dp(items, limit):
table = [[0 for w in range(limit + 1)] for j in xrange(len(items) + 1)]
 
for j in xrange(1, len(items) + 1):
item, wt, val = items[j-1]
for w in xrange(1, limit + 1):
if wt > w:
table[j][w] = table[j-1][w]
else:
table[j][w] = max(table[j-1][w],
table[j-1][w-wt] + val)
 
result = []
w = limit
for j in range(len(items), 0, -1):
was_added = table[j][w] != table[j-1][w]
 
if was_added:
item, wt, val = items[j-1]
result.append(items[j-1])
w -= wt
 
return result
 
 
bagged = knapsack01_dp(items, 400)
print("Bagged the following items\n " +
'\n '.join(sorted(item for item,_,_ in bagged)))
val, wt = totalvalue(bagged)
print("for a total value of %i and a total weight of %i" % (val, -wt))

[edit] Racket

 
#lang racket
; An ITEM a list of three elements:
; a name, a weight, and, a value
 
; A SOLUTION to a knapsack01 problems is a list of three elements:
; the total value, the total weight, and, names of the items to bag
 
(define (add i s) ; add an item i to the solution s
(match-define (list in iw iv) i)
(match-define (list v w is) s)
(list (+ v iv) (+ w iw) (cons in is)))
 
(define (knapsack max-weight items)
 ; return a solution to the knapsack01 problem
(define ht (make-hash)) ; (weight number-of-items) -> items
(define (get w no-items) (hash-ref ht (list w no-items) #f))
(define (update w is x) (hash-set! ht (list w (length is)) is) x)
(define (knapsack1 left items)
 ; return a solution to the (left, items) problem
(cond
 ; if there are no items, then bag no items:
[(empty? items) (list 0 0 '())]
 ; look up the best solution:
[(or (get left (length items))
 ; the solution haven't been cached, so we
 ; must compute it and update the cache:
(update
left items
(match items
 ; let us name the first item
[(cons (and (list i w v) x) more)
 ; if the first item weighs more than the space left,
 ; we simply find a solution, where it is omitted:
(cond [(> w left) (knapsack left more)]
 ; there is room for the first item, but
 ; we need to choose the best solutions
 ; between those with it and that without:
[else
(define without (knapsack left more))
(define value-without (first without))
(define with (knapsack (- left w) more))
(define value-with (+ (first with) v))
 ; choose the solutions with greatest value
(if (> value-without value-with)
without
(add x with))])])))]))
(knapsack1 max-weight items))
 
(knapsack 400
'((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)
(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 compass water sandwich glucose banana cream trousers overclothes notecase glasses socks))
 

[edit] R

 
Full_Data<-structure(list(item = c("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"), weigth = c(9, 13, 153, 50, 15, 68, 27, 39,
23, 52, 11, 32, 24, 48, 73, 42, 43, 22, 7, 18, 4, 30), value = c(150,
35, 200, 160, 60, 45, 60, 40, 30, 10, 70, 30, 15, 10, 40, 70,
75, 80, 20, 12, 50, 10)), .Names = c("item", "weigth", "value"
), row.names = c(NA, 22L), class = "data.frame")
 
 
Bounded_knapsack<-function(Data,W)
{
K<-matrix(NA,nrow=W+1,ncol=dim(Data)[1]+1)
0->K[1,]->K[,1]
matrix_item<-matrix('',nrow=W+1,ncol=dim(Data)[1]+1)
for(j in 1:dim(Data)[1])
{
for(w in 1:W)
{
wj<-Data$weigth[j]
item<-Data$item[j]
value<-Data$value[j]
if( wj > w )
{
K[w+1,j+1]<-K[w+1,j]
matrix_item[w+1,j+1]<-matrix_item[w+1,j]
}
else
{
if( K[w+1,j] >= K[w+1-wj,j]+value )
{
K[w+1,j+1]<-K[w+1,j]
matrix_item[w+1,j+1]<-matrix_item[w+1,j]
}
else
{
K[w+1,j+1]<-K[w+1-wj,j]+value
matrix_item[w+1,j+1]<-item
}
}
}
}
return(list(K=K,Item=matrix_item))
}
 
backtracking<-function(knapsack, Data)
{
W<-dim(knapsack$K)[1]
itens<-c()
col<-dim(knapsack$K)[2]
selected_item<-knapsack$Item[W,col]
while(selected_item!='')
{
selected_item<-knapsack$Item[W,col]
if(selected_item!='')
{
selected_item_value<-Data[Data$item == selected_item,]
if(-knapsack$K[W - selected_item_value$weigth,col-1]+knapsack$K[W,col]==selected_item_value$value)
{
W <- W - selected_item_value$weigth
itens<-c(itens,selected_item)
}
col <- col - 1
}
}
return(itens)
}
 
print_output<-function(Data,W)
{
Bounded_knapsack(Data,W)->Knap
backtracking(Knap, Data)->Items
output<-paste('You must carry:', paste(Items, sep = ', '), sep=' ' )
return(output)
}
 
print_output(Full_Data, 400)
 
 

Output:

 
[1] "You must carry: socks"
[2] "You must carry: sunglasses"
[3] "You must carry: note-case"
[4] "You must carry: waterproof_overclothes"
[5] "You must carry: waterproof_trousers"
[6] "You must carry: suntan_cream"
[7] "You must carry: banana"
[8] "You must carry: glucose"
[9] "You must carry: sandwich"
[10] "You must carry: water"
[11] "You must carry: compass"
[12] "You must carry: map"
 

[edit] REXX

Originally, the combination generator/checker subroutine (SIM) was recursive and made the program solution generic (and very concise).

However, a recursive solution also made the solution much more slower, so the combination generator/checker was "unrolled" and converted into discrete combination checks (based on the number of items). The unused combinatorial checks were discarded and only the pertinent code was retained. It made no sense to include all the unused subroutines here as space appears to be a premium for some entries in Rosetta Code.

/*REXX pgm solves a knapsack problem (22 items with weight restriction).*/
@.=
@.1 = 'map 9 150'
@.2 = 'compass 13 35'
@.3 = 'water 153 200'
@.4 = 'sandwich 50 160'
@.5 = 'glucose 15 60'
@.6 = 'tin 68 45'
@.7 = 'banana 27 60'
@.8 = 'apple 39 40'
@.9 = 'cheese 23 30'
@.10 = 'beer 52 10'
@.11 = 'suntan_cream 11 70'
@.12 = 'camera 32 30'
@.13 = 'T-shirt 24 15'
@.14 = 'trousers 48 10'
@.15 = 'umbrella 73 40'
@.16 = 'waterproof_trousers 42 70'
@.17 = 'waterproof_overclothes 43 75'
@.18 = 'note-case 22 80'
@.19 = 'sunglasses 7 20'
@.20 = 'towel 18 12'
@.21 = 'socks 4 50'
@.22 = 'book 30 10'
maxWeight=400 /*the maximum weight for knapsack*/
say; say 'maximum weight allowed for a knapsack:' comma(maxWeight); say
maxL=length('item') /*maximum width for table names. */
maxL=length('knapsack items') /*maximum width for table names. */
maxW=length('weight') /* " " " " weights*/
maxV=length('value') /* " " " " values.*/
maxQ=length('pieces') /* " " " " quant. */
highQ=0 /*max quantity specified (if any)*/
items=0; i.=; w.=0; v.=0; q.=0; Tw=0; Tv=0; Tq=0 /*initialize stuff.*/
/*────────────────────────────────sort the choices by decreasing weight.*/
/*this minimizes # combinations. */
do j=1 while @.j\=='' /*process each choice and sort. */
_=@.j; _wt=word(_,2) /*choose first item (arbitrary). */
_wt=word(_,2)
do k=j+1 while @.k\=='' /*find a possible heavier item. */
 ?wt=word(@.k,2)
if ?wt>_wt then do; _=@.k; @.k=@.j; @.j=_; _wt=?wt; end
end /*k*/
end /*j*/
obj=j-1 /*adjust for the DO loop index. */
/*────────────────────────────────build list of choices.────────────────*/
do j=1 for obj /*build a list of choices. */
_=space(@.j) /*remove superfluous blanks. */
parse var _ item w v q . /*parse original choice for table*/
if w>maxWeight then iterate /*if the weight > maximum, ignore*/
Tw=Tw+w; Tv=Tv+v; Tq=Tq+1 /*add totals up (for alignment). */
maxL=max(maxL,length(item)) /*find maximum width for item. */
if q=='' then q=1
highQ=max(highQ,q)
items=items+1 /*bump the item counter. */
i.items=item; w.items=w; v.items=v; q.items=q
do k=2 to q; items=items+1 /*bump the item counter. */
i.items=item; w.items=w; v.items=v; q.items=q
Tw=Tw+w; Tv=Tv+v; Tq=Tq+1
end /*k*/
end /*j*/
 
maxW=max(maxW,length(comma(Tw))) /*find maximum width for weight. */
maxV=max(maxV,length(comma(Tv))) /* " " " " value. */
maxQ=max(maxQ,length(comma(Tq))) /* " " " " quantity*/
maxL=maxL+maxL%4+4 /*extend width of name for table.*/
/*────────────────────────────────show the list of choices.─────────────*/
call hdr 'item'; do j=1 for obj /*show all choices, nice format. */
parse var @.j item weight value q .
if highq==1 then q=
else if q=='' then q=1
call show item,weight,value,q
end /*j*/
 
say; say 'number of items:' items; say
/*─────────────────────────────────────examine the possible choices. */
h=items; ho=h+1; m=maxWeight; $=0; call sim22
/*─────────────────────────────────────show the best choice (weight,val)*/
do h-1;  ?=strip(strip(?),"L",0); end
bestC=?; bestW=0; bestV=$; highQ=0; totP=words(bestC)
call hdr 'best choice'
do j=1 to totP /*J is modified within DO loop. */
_=word(bestC,j); _w=w._; _v=v._; q=1
if _==0 then iterate
do k=j+1 to totP
__=word(bestC,k); if i._\==i.__ then leave
j=j+1; w._=w._+_w; v._=v._+_v; q=q+1
end /*k*/
call show i._,w._,v._,q; bestW=bestw+w._
end /*j*/
call hdr2; say
call show 'best weight' ,bestW /*show a nicely formatted winnerW*/
call show 'best value' ,,bestV /*show a nicely formatted winnerV*/
call show 'knapsack items',,,totP /*show a nicely formatted pieces.*/
exit /*stick a fork in it, we're done.*/
/*────────────────────────────────COMMA subroutine──────────────────────*/
comma: procedure; parse arg _,c,p,t;arg ,cu;c=word(c ",",1)
if cu=='BLANK' then c=' ';o=word(p 3,1);p=abs(o);t=word(t 999999999,1)
if \datatype(p,'W')|\datatype(t,'W')|p==0|arg()>4 then return _;n=_'.9'
#=123456789;k=0;if o<0 then do;b=verify(_,' ');if b==0 then return _
e=length(_)-verify(reverse(_),' ')+1;end;else do;b=verify(n,#,"M")
e=verify(n,#'0',,verify(n,#"0.",'M'))-p-1;end
do j=e to b by -p while k<t;_=insert(c,_,j);k=k+1;end;return _
/*────────────────────────────────HDR subroutine────────────────────────*/
hdr: parse arg _item_,_; if highq\==1 then _=center('pieces',maxq)
call show center( _item_ ,maxL),,
center('weight',maxW),,
center('value' ,maxV),,
center(_ ,maxQ)
call hdr2
return
/*────────────────────────────────HDR2 subroutine───────────────────────*/
hdr2: _=maxQ; if highq==1 then _=0; call show copies('=' ,maxL),,
copies('=' ,maxW),,
copies('=' ,maxV),,
copies('=' ,_ )
return
/*────────────────────────────────J? subroutine─────────────────────────*/
j?: parse arg _,?; $=value('V'_); do j=1 for _; ?=? value('J'j); end; return
/*────────────────────────────────SHOW subroutine───────────────────────*/
show: parse arg _item,_weight,_value,_quant
say translate(left(_item,maxL,'─'),,'_'),
right(comma(_weight),maxW),
right(comma(_value ),maxV),
right(comma(_quant ),maxQ)
return
/*────────────────────────────────SIM22 subroutine──────────────────────*/
sim22: do j1=0 for h+1; w1=w.j1;v1=v.j1;if v1>$ then call j? 1
do j2=j1+(j1\==0) to h
if w.j2+w1>m then iterate j1;w2=w1+w.j2;v2=v1+v.j2;if v2>$ then call j? 2
do j3=j2+(j2\==0) to h
if w.j3+w2>m then iterate j2;w3=w2+w.j3;v3=v2+v.j3;if v3>$ then call j? 3
do j4=j3+(j3\==0) to h
if w.j4+w3>m then iterate j3;w4=w3+w.j4;v4=v3+v.j4;if v4>$ then call j? 4
do j5=j4+(j4\==0) to h
if w.j5+w4>m then iterate j4;w5=w4+w.j5;v5=v4+v.j5;if v5>$ then call j? 5
do j6=j5+(j5\==0) to h
if w.j6+w5>m then iterate j5;w6=w5+w.j6;v6=v5+v.j6;if v6>$ then call j? 6
do j7=j6+(j6\==0) to h
if w.j7+w6>m then iterate j6;w7=w6+w.j7;v7=v6+v.j7;if v7>$ then call j? 7
do j8=j7+(j7\==0) to h
if w.j8+w7>m then iterate j7;w8=w7+w.j8;v8=v7+v.j8;if v8>$ then call j? 8
do j9=j8+(j8\==0) to h
if w.j9+w8>m then iterate j8;w9=w8+w.j9;v9=v8+v.j9;if v9>$ then call j? 9
do j10=j9+(j9\==0) to h
if w.j10+w9>m then iterate j9;w10=w9+w.j10;v10=v9+v.j10;if v10>$ then call j? 10
do j11=j10+(j10\==0) to h
if w.j11+w10>m then iterate j10;w11=w10+w.j11;v11=v10+v.j11;if v11>$ then call j? 11
do j12=j11+(j11\==0) to h
if w.j12+w11>m then iterate j11;w12=w11+w.j12;v12=v11+v.j12;if v12>$ then call j? 12
do j13=j12+(j12\==0) to h
if w.j13+w12>m then iterate j12;w13=w12+w.j13;v13=v12+v.j13;if v13>$ then call j? 13
do j14=j13+(j13\==0) to h
if w.j14+w13>m then iterate j13;w14=w13+w.j14;v14=v13+v.j14;if v14>$ then call j? 14
do j15=j14+(j14\==0) to h
if w.j15+w14>m then iterate j14;w15=w14+w.j15;v15=v14+v.j15;if v15>$ then call j? 15
do j16=j15+(j15\==0) to h
if w.j16+w15>m then iterate j15;w16=w15+w.j16;v16=v15+v.j16;if v16>$ then call j? 16
do j17=j16+(j16\==0) to h
if w.j17+w16>m then iterate j16;w17=w16+w.j17;v17=v16+v.j17;if v17>$ then call j? 17
do j18=j17+(j17\==0) to h
if w.j18+w17>m then iterate j17;w18=w17+w.j18;v18=v17+v.j18;if v18>$ then call j? 18
do j19=j18+(j18\==0) to h
if w.j19+w18>m then iterate j18;w19=w18+w.j19;v19=v18+v.j19;if v19>$ then call j? 19
do j20=j19+(j19\==0) to h
if w.j20+w19>m then iterate j19;w20=w19+w.j20;v20=v19+v.j20;if v20>$ then call j? 20
do j21=j20+(j20\==0) to h
if w.j21+w20>m then iterate j20;w21=w20+w.j21;v21=v20+v.j21;if v21>$ then call j? 21
do j22=j21+(j21\==0) to h
if w.j22+w21>m then iterate j21;w22=w21+w.j22;v22=v21+v.j22;if v22>$ then call j? 22
end;end;end;end;end;end;end;end;end;end;end;end;end;end;end;end;end;end;end;end;end;end
return
Output:
maximum weight allowed for a knapsack: 400

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

number of items: 22


          best choice           weight value pieces
=============================== ====== ===== ======
water──────────────────────────    153   200      1
sandwich───────────────────────     50   160      1
waterproof overclothes─────────     43    75      1
waterproof trousers────────────     42    70      1
banana─────────────────────────     27    60      1
note-case──────────────────────     22    80      1
glucose────────────────────────     15    60      1
compass────────────────────────     13    35      1
suntan cream───────────────────     11    70      1
map────────────────────────────      9   150      1
sunglasses─────────────────────      7    20      1
socks──────────────────────────      4    50      1
=============================== ====== ===== ======

best weight────────────────────    396
best value─────────────────────        1,030
knapsack items─────────────────                  12

[edit] Ruby

[edit] Brute force

KnapsackItem = Struct.new(:name, :weight, :value)
potential_items = [
KnapsackItem.new('map', 9, 150), KnapsackItem.new('compass', 13, 35),
KnapsackItem.new('water', 153, 200), KnapsackItem.new('sandwich', 50, 160),
KnapsackItem.new('glucose', 15, 60), KnapsackItem.new('tin', 68, 45),
KnapsackItem.new('banana', 27, 60), KnapsackItem.new('apple', 39, 40),
KnapsackItem.new('cheese', 23, 30), KnapsackItem.new('beer', 52, 10),
KnapsackItem.new('suntan cream', 11, 70), KnapsackItem.new('camera', 32, 30),
KnapsackItem.new('t-shirt', 24, 15), KnapsackItem.new('trousers', 48, 10),
KnapsackItem.new('umbrella', 73, 40), KnapsackItem.new('waterproof trousers', 42, 70),
KnapsackItem.new('waterproof overclothes', 43, 75), KnapsackItem.new('note-case', 22, 80),
KnapsackItem.new('sunglasses', 7, 20), KnapsackItem.new('towel', 18, 12),
KnapsackItem.new('socks', 4, 50), KnapsackItem.new('book', 30, 10),
]
knapsack_capacity = 400
 
class Array
# do something for each element of the array's power set
def power_set
yield [] if block_given?
self.inject([[]]) do |ps, elem|
r = []
ps.each do |i|
r << i
new_subset = i + [elem]
yield new_subset if block_given?
r << new_subset
end
r
end
end
end
 
maxval = 0
solutions = []
 
potential_items.power_set do |subset|
weight = subset.inject(0) {|w, elem| w += elem.weight}
next if weight > knapsack_capacity
 
value = subset.inject(0) {|v, elem| v += elem.value}
if value == maxval
solutions << subset
elsif value > maxval
maxval = value
solutions = [subset]
end
end
 
puts "value: #{maxval}"
solutions.each do |set|
items = []
wt = 0
set.each {|elem| wt += elem.weight; items << elem.name}
puts "weight: #{wt}"
puts "items: #{items.sort.join(',')}"
end
Output:
value: 1030
weight: 396
items: banana,compass,glucose,map,note-case,sandwich,socks,sunglasses,suntan cream,water,waterproof overclothes,waterproof trousers

[edit] Dynamic Programming

Translated from http://sites.google.com/site/mikescoderama/Home/0-1-knapsack-problem-in-p

KnapsackItem = Struct.new(:name, :cost, :value)
KnapsackProblem = Struct.new(:items, :max_cost)
 
def dynamic_programming_knapsack(problem)
num_items = problem.items.size
items = problem.items
max_cost = problem.max_cost
 
cost_matrix = zeros(num_items, max_cost+1)
 
num_items.times do |i|
(max_cost + 1).times do |j|
if(items[i].cost > j)
cost_matrix[i][j] = cost_matrix[i-1][j]
else
cost_matrix[i][j] = [cost_matrix[i-1][j], items[i].value + cost_matrix[i-1][j-items[i].cost]].max
end
end
end
 
cost_matrix
end
 
def get_used_items(problem, cost_matrix)
i = cost_matrix.size - 1
currentCost = cost_matrix[0].size - 1
marked = Array.new(cost_matrix.size, 0)
 
while(i >= 0 && currentCost >= 0)
if(i == 0 && cost_matrix[i][currentCost] > 0 ) || (cost_matrix[i][currentCost] != cost_matrix[i-1][currentCost])
marked[i] = 1
currentCost -= problem.items[i].cost
end
i -= 1
end
marked
end
 
def get_list_of_used_items_names(problem, cost_matrix)
items = problem.items
used_items = get_used_items(problem, cost_matrix)
 
result = []
 
used_items.each_with_index do |item,i|
if item > 0
result << items[i].name
end
end
 
result.sort.join(', ')
end
 
def zeros(rows, cols)
Array.new(rows) do |row|
Array.new(cols, 0)
end
end
 
if $0 == __FILE__
 
items = [
KnapsackItem.new('map' , 9 , 150) , KnapsackItem.new('compass' , 13 , 35) ,
KnapsackItem.new('water' , 153 , 200) , KnapsackItem.new('sandwich' , 50 , 160) ,
KnapsackItem.new('glucose' , 15 , 60) , KnapsackItem.new('tin' , 68 , 45) ,
KnapsackItem.new('banana' , 27 , 60) , KnapsackItem.new('apple' , 39 , 40) ,
KnapsackItem.new('cheese' , 23 , 30) , KnapsackItem.new('beer' , 52 , 10) ,
KnapsackItem.new('suntan cream' , 11 , 70) , KnapsackItem.new('camera' , 32 , 30) ,
KnapsackItem.new('t-shirt' , 24 , 15) , KnapsackItem.new('trousers' , 48 , 10) ,
KnapsackItem.new('umbrella' , 73 , 40) , KnapsackItem.new('waterproof trousers' , 42 , 70) ,
KnapsackItem.new('waterproof overclothes' , 43 , 75) , KnapsackItem.new('note-case' , 22 , 80) ,
KnapsackItem.new('sunglasses' , 7 , 20) , KnapsackItem.new('towel' , 18 , 12) ,
KnapsackItem.new('socks' , 4 , 50) , KnapsackItem.new('book' , 30 , 10)
]
 
problem = KnapsackProblem.new(items, 400)
 
cost_matrix = dynamic_programming_knapsack problem
puts
puts 'Dynamic Programming:'
puts
puts 'Found solution: ' + get_list_of_used_items_names(problem, cost_matrix)
puts 'With value: ' + cost_matrix.last.last.to_s
end
Dynamic Programming:

Found solution: banana, compass, glucose, map, note-case, sandwich, socks, sunglasses, suntan cream, water, waterproof overclothes, waterproof trousers
With value: 1030

[edit] Rust

extern crate std;
use std::cmp::max;
use std::vec::Vec;
 
 
// This struct is used to store our items that we want in our knap-sack.
struct Want<'a> {
name: &'a str,
weight: uint,
value: uint
}
 
 
// Global, immutable allocation of our items.
static items : &'static [Want<'static>] = &[
Want {name: "map", weight: 9, value: 150},
Want {name: "compass", weight: 13, value: 35},
Want {name: "water", weight: 153, value: 200},
Want {name: "sandwich", weight: 50, value: 160},
Want {name: "glucose", weight: 15, value: 60},
Want {name: "tin", weight: 68, value: 45},
Want {name: "banana", weight: 27, value: 60},
Want {name: "apple", weight: 39, value: 40},
Want {name: "cheese", weight: 23, value: 30},
Want {name: "beer", weight: 52, value: 10},
Want {name: "suntancream", weight: 11, value: 70},
Want {name: "camera", weight: 32, value: 30},
Want {name: "T-shirt", weight: 24, value: 15},
Want {name: "trousers", weight: 48, value: 10},
Want {name: "umbrella", weight: 73, value: 40},
Want {name: "waterproof trousers", weight: 42, value: 70},
Want {name: "waterproof overclothes", weight: 43, value: 75},
Want {name: "note-case", weight: 22, value: 80},
Want {name: "sunglasses", weight: 7, value: 20},
Want {name: "towel", weight: 18, value: 12},
Want {name: "socks", weight: 4, value: 50},
Want {name: "book", weight: 30, value: 10}
];
 
 
// This is a bottom-up dynamic programming solution to the 0-1 knap-sack problem.
// maximize value
// subject to weights <= max_weight
fn knap_01_dp<'a>(xs: &[Want<'a>], max_weight: uint) -> Vec<Want<'a>> {
 
// Save this value, so we don't have to make repeated calls.
let xs_len = xs.len();
 
// Imagine we wrote a recursive function(item, max_weight) that returns a
// uint corresponding to the maximum cumulative value by considering a
// subset of items such that the combined weight <= max_weight.
//
// fn best_value(item: uint, max_weight: uint) -> uint{
// if item == 0 {
// return 0;
// }
// if xs[item - 1].weight > max_weight {
// return best_value(item - 1, max_weight);
// }
// return max(best_value(item - 1, max_weight),
// best_value(item - 1, max_weight - xs[item - 1].weight)
// + xs[item - 1].value);
// }
//
// best_value(xs_len, max_weight) is equal to the maximum value that we
// can add to the bag.
//
// The problem with using this function is that it performs redundant
// calculations.
//
// The dynamic programming solution is to precompute all of the values we
// need and put them into a 2D array.
//
// In a similar vein, the top-down solution would be to memoize the
// function then compute the results on demand.
 
let zero_vec = Vec::from_elem(max_weight + 1, 0 as uint);
let mut best_value = Vec::from_elem(xs_len + 1, zero_vec);
 
// loop over the items
for i in range(0, xs_len) {
// loop over the weights
for w in range(1, max_weight + 1) {
// do we have room in our knapsack?
if xs[i].weight > w {
// if we don't, then we'll say that the value doesn't change
// when considering this item
*best_value.get_mut(i + 1).get_mut(w) = best_value.get(i).get(w).clone();
} else {
// if we do, then we have to see if the value we gain by adding
// the item, given the weight, is better than not adding the item
*best_value.get_mut(i + 1).get_mut(w) =
max(best_value.get(i).get(w).clone(),
best_value.get(i).get(w - xs[i].weight) + xs[i].value);
}
}
}
 
// a variable representing the weight left in the bag
let mut left_weight = max_weight.clone();
 
// a possibly over-allocated dynamically sized vector to push results to
let mut result = Vec::with_capacity(xs_len);
 
// we built up the solution space through a forward pass over the data,
// now we have to traverse backwards to get the solution
for i in range(1, xs_len+1).rev() {
// We can check if an item should be added to the knap-sack by comparing
// best_value with and without this item. If best_value added this
// item then so should we.
if best_value.get(i).get(left_weight) != best_value.get(i - 1).get(left_weight) {
result.push(xs[i - 1]);
// we remove the weight of the object from the remaining weight
// we can add to the bag
left_weight -= xs[i - 1].weight;
}
}
 
return result;
}
 
 
fn main () {
let xs = knap_01_dp(items, 400);
 
// Print the items. We have to reverse the order because we solved the
// problem backward.
for i in xs.iter().rev() {
println!("Item: {}, Weight: {}, Value: {}", i.name, i.weight, i.value);
}
 
// Print the sum of weights.
let weights = xs.iter().fold(0, |a, &b| a + b.weight);
println!("Total Weight: {}", weights);
 
// Print the sum of the values.
let values = xs.iter().fold(0, |a, &b| a + b.value);
println!("Total Value: {}", values);
 
}
Output:
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: suntancream, 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
Total Weight: 396
Total Value: 1030

[edit] Scala

Works with: Scala version 2.9.2
object Knapsack extends App {
 
case class Item(name: String, weight: Int, value: Int)
 
val elapsed: (=> Unit) => Long = f => {val s = System.currentTimeMillis; f; (System.currentTimeMillis - s)/1000}
 
//===== brute force (caution: increase the heap!) ====================================
val ks01b: List[Item] => Unit = loi => {
val tw:Set[Item]=>Int=ps=>(ps:\0)((a,b)=>a.weight+b) //total weight
val tv:Set[Item]=>Int=ps=>(ps:\0)((a,b)=>a.value+b) //total value
val pis = (loi.toSet.subsets).toList.filterNot(_==Set())
 
#[test]
fn test_dp_results() {
let dp_results = knap_01_dp(items, 400);
let dp_weights= dp_results.iter().fold(0, |a, &b| a + b.weight);
let dp_values = dp_results.iter().fold(0, |a, &b| a + b.value);
assert_eq!(dp_weights, 396);
assert_eq!(dp_values, 1030);
} val res = pis.map(ss=>Pair(ss,tw(ss)))
.filter(p=>p._2>350 && p._2<401).map(p=>Pair(p,tv(p._1)))
.sortWith((s,t)=>s._2.compareTo(t._2) < 0)
.last
println{val h = "packing list of items (brute force):"; h+"\n"+"="*h.size}
res._1._1.foreach{p=>print(" "+p.name+": weight="+p.weight+" value="+p.value+"\n")}
println("\n"+" resulting items: "+res._1._1.size+" of "+loi.size)
println(" total weight: "+res._1._2+", total value: "+res._2)
}
 
//===== dynamic programming ==========================================================
val ks01d: List[Item] => Unit = loi => {
val W = 400
val N = loi.size
 
val m = Array.ofDim[Int](N+1,W+1)
val plm = (List((for {w <- 0 to W} yield Set[Item]()).toArray)++(
for {
n <- 0 to N-1
colN = (for {w <- 0 to W} yield Set[Item](loi(n))).toArray
} yield colN)).toArray
 
1 to N foreach {n =>
0 to W foreach {w =>
def in = loi(n-1)
def wn = loi(n-1).weight
def vn = loi(n-1).value
if (w<wn) {
m(n)(w) = m(n-1)(w)
plm(n)(w) = plm(n-1)(w)
}
else {
if (m(n-1)(w)>=m(n-1)(w-wn)+vn) {
m(n)(w) = m(n-1)(w)
plm(n)(w) = plm(n-1)(w)
}
else {
m(n)(w) = m(n-1)(w-wn)+vn
plm(n)(w) = plm(n-1)(w-wn)+in
}
}
}
}
 
println{val h = "packing list of items (dynamic programming):"; h+"\n"+"="*h.size}
plm(N)(W).foreach{p=>print(" "+p.name+": weight="+p.weight+" value="+p.value+"\n")}
println("\n"+" resulting items: "+plm(N)(W).size+" of "+loi.size)
println(" total weight: "+(0/:plm(N)(W).map{item=>item.weight})(_+_)+", total value: "+m(N)(W))
}
 
val items = List(
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)
)
 
List(ks01b, ks01d).foreach{f=>
val t = elapsed{f(items)}
println(" elapsed time: "+t+" sec"+"\n")
}
}

Output:

packing list of items (brute force):
====================================
  waterproof overclothes: weight=43 value=75
  note-case: weight=22 value=80
  socks: weight=4 value=50
  sandwich: weight=50 value=160
  banana: weight=27 value=60
  glucose: weight=15 value=60
  map: weight=9 value=150
  water: weight=153 value=200
  suntan cream: weight=11 value=70
  sunglasses: weight=7 value=20
  waterproof trousers: weight=42 value=70
  compass: weight=13 value=35

  resulting items: 12 of 22
  total weight: 396, total value: 1030
  elapsed time: 19 sec

packing list of items (dynamic programming):
============================================
  waterproof overclothes: weight=43 value=75
  note-case: weight=22 value=80
  socks: weight=4 value=50
  sandwich: weight=50 value=160
  banana: weight=27 value=60
  glucose: weight=15 value=60
  map: weight=9 value=150
  water: weight=153 value=200
  suntan cream: weight=11 value=70
  sunglasses: weight=7 value=20
  waterproof trousers: weight=42 value=70
  compass: weight=13 value=35

  resulting items: 12 of 22
  total weight: 396, total value: 1030
  elapsed time: 0 sec

[edit] SQL

A brute force solution that runs in SQL Server 2005 or later using a recursive CTE. Displays the top 5 solutions and runs in about 39 seconds.

 
WITH KnapsackItems (item, [weight], VALUE) AS
(
SELECT 'map',9, 150
UNION ALL SELECT 'compass',13, 35
UNION ALL SELECT 'water',153, 200
UNION ALL SELECT 'sandwich',50, 160
UNION ALL SELECT 'glucose',15, 60
UNION ALL SELECT 'tin',68, 45
UNION ALL SELECT 'banana',27, 60
UNION ALL SELECT 'apple',39, 40
UNION ALL SELECT 'cheese',23, 30
UNION ALL SELECT 'beer',52, 10
UNION ALL SELECT 'suntan cream',11, 70
UNION ALL SELECT 'camera',32, 30
UNION ALL SELECT 'T-shirt',24, 15
UNION ALL SELECT 'trousers',48, 10
UNION ALL SELECT 'umbrella',73, 40
UNION ALL SELECT 'waterproof trousers',42, 70
UNION ALL SELECT 'waterproof overclothes',43, 75
UNION ALL SELECT 'note-case',22, 80
UNION ALL SELECT 'sunglasses',7, 20
UNION ALL SELECT 'towel',18, 12
UNION ALL SELECT 'socks',4, 50
UNION ALL SELECT 'book',30, 10
)
SELECT *
INTO #KnapsackItems
FROM KnapsackItems;
 
WITH UNIQUEnTuples (n, Tuples, ID, [weight], VALUE) AS (
SELECT 1, CAST(item AS VARCHAR(8000)), item, [weight], VALUE
FROM #KnapsackItems
UNION ALL
SELECT 1 + n.n, t.item + ',' + n.Tuples, item, n.[weight] + t.[weight], n.VALUE + t.VALUE
FROM UNIQUEnTuples n
CROSS APPLY (
SELECT item, [weight], VALUE
FROM #KnapsackItems t
WHERE t.item < n.ID AND n.[weight] + t.[weight] < 400) t
)
SELECT TOP 5 *
FROM UNIQUEnTuples
ORDER BY VALUE DESC, n, Tuples;
 
GO
DROP TABLE #KnapsackItems;
 
Output:
weight  value  Solution
396     1030   banana,compass,glucose,map,note-case,sandwich,socks,sunglasses,suntan cream,water,waterproof overclothes,waterproof trousers
389     1010   banana,compass,glucose,map,note-case,sandwich,socks,suntan cream,water,waterproof overclothes,waterproof trousers
399     1005   banana,cheese,glucose,map,note-case,sandwich,socks,suntan cream,water,waterproof overclothes,waterproof trousers
395     1002   banana,cheese,compass,glucose,map,note-case,sandwich,socks,sunglasses,suntan cream,towel,water,waterproof overclothes
393     1000   apple,banana,compass,glucose,map,note-case,sandwich,socks,sunglasses,suntan cream,water,waterproof overclothes

[edit] Tcl

As the saying goes, “when in doubt, try brute force”. Since there's only 22 items we can simply iterate over all possible choices.

# The list of items to consider, as list of lists
set 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}
}
 
# Simple extraction functions
proc names {chosen} {
set names {}
foreach item $chosen {lappend names [lindex $item 0]}
return $names
}
proc weight {chosen} {
set weight 0
foreach item $chosen {incr weight [lindex $item 1]}
return $weight
}
proc value {chosen} {
set value 0
foreach item $chosen {incr value [lindex $item 2]}
return $value
}
 
# Recursive function for searching over all possible choices of items
proc knapsackSearch {items {chosen {}}} {
# If we've gone over the weight limit, stop now
if {[weight $chosen] > 400} {
return
}
# If we've considered all of the items (i.e., leaf in search tree)
# then see if we've got a new best choice.
if {[llength $items] == 0} {
global best max
set v [value $chosen]
if {$v > $max} {
set max $v
set best $chosen
}
return
}
# Branch, so recurse for chosing the current item or not
set this [lindex $items 0]
set rest [lrange $items 1 end]
knapsackSearch $rest $chosen
knapsackSearch $rest [lappend chosen $this]
}
 
# Initialize a few global variables
set best {}
set max 0
# Do the brute-force search
knapsackSearch $items
# Pretty-print the results
puts "Best filling has weight of [expr {[weight $best]/100.0}]kg and score [value $best]"
puts "Best items:\n\t[join [lsort [names $best]] \n\t]"
Output:
Best filling has weight of 3.96kg and score 1030
Best items:
	banana
	compass
	glucose
	map
	note-case
	sandwich
	socks
	sunglasses
	suntan cream
	water
	waterproof overclothes
	waterproof trousers

[edit] Ursala

This solution follows a very similar approach to the one used in Knapsack problem/Bounded#Ursala, which is to treat it as a mixed integer programming problem and solve it using an off-the-shelf library (lpsolve).

#import std
#import nat
#import flo
#import lin
 
#import nat
 
items = # name: (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)>
 
system =
 
linear_system$[
binaries: ~&nS,
lower_bounds: {'(slack)': 0.}!,
costs: * ^|/~& negative+ float@r,
equations: ~&iNC\400.+ :/(1.,'(slack)')+ * ^|rlX/~& float@l]
 
#show+
 
main = ~&tnS solution system items

Binary valued variables are a more specific constraint than the general mixed integer programming problem, but can be accommodated as shown using the binaries field in the linear_system specification. The additional slack variable is specified as continuous and non-negative with no cost or benefit so as to make the constraint equation solvable without affecting the solution.

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

[edit] XPL0

include c:\cxpl\codes;  \include 'code' declarations
 
int Item, Items, Weights, Values,
BestItems, BestValues,
I, W, V, N;
def Tab=9;
def Name, Weight, Value;
[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]];
 
BestValues:= 0;
for Items:= 0 to 1<<22-1 do \for all possible combinations of Items...
[I:= Items; W:= 0; V:= 0; N:= 0;
while I do \add weights and values for each item (bit in I)
[if I&1 then
[W:= W + Item(N,Weight); V:= V + Item(N,Value)];
I:= I>>1; N:= N+1;
];
if V>BestValues & W<=400 then \save best combination found so far
[BestValues:= V; BestItems:= Items];
];
 
I:= BestItems; W:= 0; V:= 0; N:= 0; \show best combination of items
while I do
[if I&1 then
[Text(0, " "); Text(0, Item(N,Name)); ChOut(0, Tab);
IntOut(0, Item(N,Weight)); ChOut(0, Tab);
IntOut(0, Item(N,Value)); CrLf(0);
W:= W + Item(N,Weight);
V:= V + Item(N,Value);
];
I:= I>>1; N:= N+1;
];
Text(0, "Totals: ");
IntOut(0, W); ChOut(0, Tab);
IntOut(0, V); CrLf(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
Personal tools
Namespaces

Variants
Actions
Community
Explore
Misc
Toolbox