user
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.

Task

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

[dag = decagram = 10 grams]

Related tasks

* Knapsack problem/Bounded
* Knapsack problem/Unbounded
* Knapsack problem/Continuous
* A\* search algorithm
assistant
(formerly Perl 6)

#### Brute force

**Works with**: Rakudo version 2017.01

```
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 = flat 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:

```
Value = 1030
Tourist put in the bag:
  socks sunglasses note-case waterproof overclothes waterproof trousers suntan cream banana glucose sandwich water compass map
```

#### Dynamic programming

Much faster than the previous example.

**Translation of**: Perl

```
my $raw = q:to/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 $raw.lines.sort({-($_ ~~ m/\d+/)}).comb(/\S+[\s\S+]*/) -> $n, $w, $v {
    @name.push:   $n;
    @weight.push: $w;
    @value.push:  $v;
}

my $sum = 400;

my @subset;

sub optimal ($item, $sub-sum) {
    return 0, [] if $item < 0;
    return |@subset[$item][$sub-sum] if @subset[$item][$sub-sum];

    my @next = optimal($item-1, $sub-sum);

    if @weight[$item] > $sub-sum {
        @subset[$item][$sub-sum] = @next
    } else {
        my @skip = optimal($item-1, $sub-sum - @weight[$item]);

        if (@next[0] > @skip[0] + @value[$item] ) {
            @subset[$item][$sub-sum] = @next;
        } else {
            @subset[$item][$sub-sum] = @skip[0] + @value[$item], [|@skip[1], @name[$item]];
        }
    }

    |@subset[$item][$sub-sum]
}

my @solution = optimal(@name.end, $sum);
put "@solution[0]: ", @solution[1].sort.join(', ');

```

Output:

```
1030: banana, compass, glucose, map, note-case, sandwich, socks, sunglasses, suntancream, water, waterproof overclothes, waterproof trousers

```