user
A thief burgles a butcher's shop, where he can select from some items.

The thief knows the weights and prices of each items.   Because he has a knapsack with 15 kg maximal capacity, he wants to select the items such that he would have his profit maximized.   He may cut the items;   the item has a reduced price after cutting that is proportional to the original price by the ratio of masses.   That means:   half of an item has half the price of the original.

This is the item list in the butcher's shop:

:   :   :   :   :   :   Table of potential knapsack items

                        | Item | Weight (kg) | Price (Value) |
                        | --- | --- | --- |
                        | beef | 3.8 | 36 |
                        | pork | 5.4 | 43 |
                        | ham | 3.6 | 90 |
                        | greaves | 2.4 | 45 |
                        | flitch | 4.0 | 30 |
                        | brawn | 2.5 | 56 |
                        | welt | 3.7 | 67 |
                        | salami | 3.0 | 95 |
                        | sausage | 5.9 | 98 |
                        | Knapsack | <=15 kg | ? |

Task

Show which items the thief carries in his knapsack so that their total weight does not exceed 15 kg, and their total value is maximized.

Related tasks

* Knapsack problem/Bounded
* Knapsack problem/Unbounded
* Knapsack problem/0-1

See also

* Wikipedia article:   continuous knapsack.
assistant
(formerly Perl 6)

**Works with**: rakudo version 2015-09-16

This Solutions sorts the item by WEIGHT/VALUE

```
class KnapsackItem {
  has $.name;
  has $.weight is rw;
  has $.price is rw;
  has $.ppw;

  method new (Str $n, Rat $w, Int $p) {
    self.bless(:name($n), :weight($w), :price($p), :ppw($w/$p))
  }

  method cut-maybe ($max-weight) {
    return False if $max-weight > $.weight;
    $.price = $max-weight / $.ppw;
    $.weight = $.ppw * $.price;
    return True;
  }

  method gist () { sprintf "%8s %1.2f   %3.2f",
                            $.name,
                                $.weight,
                                        $.price }
}

my $max-w = 15;
say    "Item    Portion Value";

.say for gather
    for < beef    3.8 36
          pork    5.4 43
          ham     3.6 90
          greaves 2.4 45
          flitch  4.0 30
          brawn   2.5 56
          welt    3.7 67
          salami  3.0 95
          sausage 5.9 98 >
        ==> map({ KnapsackItem.new($^a, $^b, $^c) })
        ==> sort *.ppw
    {
        my $last-one = .cut-maybe($max-w);
        take $_;
        $max-w -= .weight;
        last if $last-one;
    }

```

**Output:**

```
Item    Portion Value
  salami 3.00   95.00
     ham 3.60   90.00
   brawn 2.50   56.00
 greaves 2.40   45.00
    welt 3.50   63.38
```