

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.


 
Module Knapsack {
      Form 60, 40
      Cls 5, 0
      Pen 14
      Class Quick {
      Private:
            partition=lambda-> {
                  Read &A(), p, r : i = p-1 : x=A(r)
                  For j=p to r-1 {If .LE(A(j), x) Then i++:Swap A(i),A(j)
                  } : Swap A(i+1), A(r) :  Push  i+2, i 
            }
      Public:
            LE=Lambda->Number<=Number
            \\ module for strings erased here
            Function quicksort {
                 Read ref$
                 {
                         loop : If Stackitem() >= Stackitem(2) Then Drop 2 : if  empty then {Break} else continue
                         over 2,2 : call .partition(ref$) :shift 3 
                 }
            }
      }
      Class Item {
            name$, weight, aValue  ' can't use Value has other meaning
            class:
            Module Item (.name$, .weight, .aValue) {}
      }
      Def Double max_weight=15, total_weight, total_value, frac
      Def long I
      Dim Items(1 to 9)
      Flush  ' empty stack
      \\ now fill stack
      Data  "beef", 3.8, 36,"pork", 5.4, 43,"ham", 3.6, 90, "greaves", 2.4, 45, "flitch", 4, 30
      Data "brawn", 2.5, 56, "welt", 3.7, 67, "salami", 3, 95, "sausage", 5.9, 98
      For i=1 to 9 : Items(i)=Item(Letter$, Number, Number): Next i
      \\ Setup QuickSort
      Quick=Quick()
      Quick.LE=lambda (b, a)-> {
            =a.avalue/a.weight<=b.avalue/b.weight
      }
      Call Quick.QuickSort(&items(), 1, 9)
      \\ So now we have a sorted array of objects
      i=0
      \\ Setup console to print
      Dim Back(-1 to 0)
      Back(-1)=#666666, #444444
      Alter=True
      \\ $("0.00", 20) Set number rounding for print, and 14 chars column width
      \\ $(2) set center justify for non proportional print
      \\ $(0) set default - strings justify left, numbers right
      Print  $("0.00", 20),$(2),"", "Knapsack"
      Pen 0 {
            Print @(pos, row,width,row+1, 7),"Item", "Weight (Kg)", "Price (value)", $(0)
      }
      While i<Len(Items()) and total_weight<max_weight {
            i++
            if total_weight+items(i).weight<max_weight Then {
                  total_weight+=items(i).weight
                  total_value+=items(i).avalue
                  WriteItem(i, 1)
            } Else {
                  frac=(max_weight-total_weight)/items(i).weight
                  total_weight+=items(i).weight*frac
                  total_value+=items(i).avalue*frac
                  WriteItem(i, frac )
            }
      }
      Print
      Pen 0 {
            Print @(pos+1, row,width,row+1, 7, 7), "Total Weight",total_weight
            Print @(pos+1, row,width,row+1, 7, 7), "Total Value", total_value
      }
      End
      Sub WriteItem(i, frac)
            For Items(i) {
                  Print @(pos+1, row,width,row+1, back(alter), 14),  .name$, .weight*frac, .avalue*frac
                  Alter~
            }
      End Sub
}
Knapsack
 