0-1

Brute force

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.

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

Last updated