gistfile1.txt

class knapsackItem{
  has string $!name; has int $!weight;has int $!unit
  method ToString(-->string) {
    return self.name ~ ' ' ~ self.weight ~ ' ' ~ self.unit
  }
}
sub makeItem(string $n, int $w, int $u --> knapsackItem) {
	my $i = knapsackItem.new;
	$i.name = $n; $i.weight = $w; $i.unit = $u;
	return $i
}

sub func(List[knapsackItem] @a, int $w, int $v --> List[knapsackItem]){
  #say($w ~ ' ' ~ $v);
  if ($w == 0 || @a.Count == 0) {
    my $z = List[knapsackItem].new();
	$z.Add(makeItem('',0,$v));
    return $z;
  }
  my @rest = @a.GetRange(1, @a.Count - 1);
  my $i = @a[0];
  my @skip = func(@rest,$w,$v);
  if ($w >= $i.weight) { # next one fits
    my @put = func( @rest,$w - $i.weight,$v + $i.unit);
    if (@put[0].unit > @skip[0].unit) {
	  my @rr = @put.GetRange(0, @put.Count);
	  @rr.Add($i);
	  return @rr
	}
  }
  return @skip
}

my $MAX_WEIGHT = 400;
my $l = List[knapsackItem].new;

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

my @res = func($l,$MAX_WEIGHT,0);
@res.RemoveAt(0);
my $w = 0;
my $v = 0;
loop (my $k = 0; $k < @res.Count; $k++) { say(@res[$k]); $w = $w + @res[$k].weight; $v = $v + @res[$k].unit }
say("value: $v weight: $w");