user
A traveler gets diverted and has to make an unscheduled stop in what turns out to be Shangri La.   Opting to leave, he is allowed to take as much as he likes of the following items, so long as it will fit in his knapsack, and he can carry it.

He knows that he can carry no more than   25   'weights' in total;   and that the capacity of his knapsack is   0.25   'cubic lengths'.

Looking just above the bar codes on the items he finds their weights and volumes.   He digs out his recent copy of a financial paper and gets the value of each item.

|  |  |  |  |  |
| --- | --- | --- | --- | --- |
| Item | Explanation | Value (each) | weight | Volume (each) |
| panacea (vials of) | Incredible healing properties | 3000 | 0.3 | 0.025 |
| ichor (ampules of) | Vampires blood | 1800 | 0.2 | 0.015 |
| gold (bars) | Shiney shiney | 2500 | 2.0 | 0.002 |
| Knapsack | For the carrying of | - | <=25 | <=0.25 |

He can only take whole units of any item, but there is much more of any item than he could ever carry

Task

Show how many of each item does he take to maximize the value of items he is carrying away with him.

Note

* There are four solutions that maximize the value taken.   Only one *need* be given.

Related tasks

* Knapsack problem/Bounded
* Knapsack problem/Continuous
* Knapsack problem/0-1
assistant
(formerly Perl 6)

**Works with**: rakudo version 2019.03.1

Brute force, looked a lot at the Ruby solution.

```
class KnapsackItem {
  has $.volume;
  has $.weight;
  has $.value;
  has $.name;

  method new($volume,$weight,$value,$name) {
    self.bless(:$volume, :$weight, :$value, :$name)
  }
};

my KnapsackItem $panacea .= new: 0.025, 0.3, 3000, "panacea";
my KnapsackItem $ichor   .= new: 0.015, 0.2, 1800, "ichor";
my KnapsackItem $gold    .= new: 0.002, 2.0, 2500, "gold";
my KnapsackItem $maximum .= new: 0.25,  25,  0   , "max";

my $max_val = 0;
my @solutions;
my %max_items;

for $panacea, $ichor, $gold -> $item {
    %max_items{$item.name} = floor min
                            $maximum.volume / $item.volume,
			    $maximum.weight / $item.weight;
}

for 0..%max_items<panacea>
       X 0..%max_items<ichor>
           X 0..%max_items<gold>
 -> ($p, $i, $g)
{
  next if $panacea.volume * $p + $ichor.volume * $i + $gold.volume * $g > $maximum.volume;
  next if $panacea.weight * $p + $ichor.weight * $i + $gold.weight * $g > $maximum.weight;
  given $panacea.value * $p + $ichor.value * $i + $gold.value * $g {
    if $_ > $max_val { $max_val = $_; @solutions = (); }
    when $max_val    { @solutions.push: $[$p,$i,$g] }
  }
}

say "maximum value is $max_val\npossible solutions:";
say "panacea\tichor\tgold";
.join("\t").say for @solutions;

```

**Output:**

```
maximum value is 54500
possible solutions:
panacea	ichor	gold
0	15	11
3	10	11
6	5	11
9	0	11
```