
my %weight = (ruby => 7, "bag of gold" => 20, carrot => 1);
my %value = (ruby => 20, "bag of gold", 15, carrot => 1);

sub subsets { 
  my @items = @_; 
  return [] if @items == 0;
  my ($first, @rest) = @items; 
  my @ss = subsets(@rest); 
  return @ss, map {[$first, @$_] } @ss;
}

sub value {
  addup($_[0], \%value);
}

sub weight {
  addup($_[0], \%weight);
}

sub addup {
  my ($set, $h) = @_;
  my $total = 0;
  for my $i (@$set) {
    $total += $h->{$i};
  }
  $total;
}

my ($MAX) = @ARGV;
my $maxval = 0;

for my $subset (subsets (keys %weight)) {
  next unless weight($subset) <= $MAX;
  my $val = value($subset);
  next if $val <= $maxval;
  print "$val: @$subset\n";
  $maxval = $val;
}
