

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.


Structure item
  name.s
  weight.f   ;units are kilograms (kg)
  Value.f
  vDensity.f ;the density of the value, i.e. value/weight, and yes I made up the term ;)
EndStructure
 
#maxWeight = 15
Global itemCount = 0 ;this will be increased as needed to match actual count
Global Dim items.item(itemCount)
 
Procedure addItem(name.s, weight.f, Value.f)
  If itemCount >= ArraySize(items())
    Redim items.item(itemCount + 10)
  EndIf
  With items(itemCount)
    \name = name
    \weight = weight
    \Value = Value
    If Not \weight
      \vDensity = \Value
    Else 
      \vDensity = \Value / \weight
    EndIf 
  EndWith
  itemCount + 1
EndProcedure
 
;build item list
addItem("beef", 3.8, 36)
addItem("pork", 5.4, 43)
addItem("ham", 3.6, 90)
addItem("greaves", 2.4, 45)
addItem("flitch", 4.0, 30)
addItem("brawn", 2.5, 56)
addItem("welt", 3.7, 67)
addItem("salami", 3.0, 95)
addItem("sausage", 5.9, 98)
SortStructuredArray(items(), #PB_Sort_descending, OffsetOf(item\vDensity), #PB_Sort_Float, 0, itemCount - 1)
 
Define TotalWeight.f, TotalValue.f, i
NewList knapsack.item()
For i = 0 To itemCount
  If TotalWeight + items(i)\weight < #maxWeight
    AddElement(knapsack())
    knapsack() = items(i)
    TotalWeight + items(i)\weight
    TotalValue + items(i)\Value
  Else
    AddElement(knapsack())
    knapsack() = items(i)
    knapsack()\weight = #maxWeight - TotalWeight
    knapsack()\Value = knapsack()\weight * knapsack()\vDensity
    TotalWeight = #maxWeight
    TotalValue + knapsack()\Value
    Break
  EndIf 
Next
 
If OpenConsole()
  PrintN(LSet("Maximal weight", 26, " ") + "= " + Str(#maxWeight) + " kg")
  PrintN(LSet("Total weight of solution", 26, " ") + "= " + Str(#maxWeight) + " kg")
  PrintN(LSet("Total value", 26, " ") + "= " + StrF(TotalValue, 3) + " " + #CRLF$)
  PrintN("You can carry the following materials in the knapsack: ")
  ForEach knapsack()
    PrintN(RSet(StrF(knapsack()\weight, 1), 5, " ") + " kg  " + LSet(knapsack()\name, 10, " ") + "  (Value = " + StrF(knapsack()\Value, 3) + ")")
  Next 
 
  Print(#CRLF$ + #CRLF$ + "Press ENTER to exit")
  Input()
  CloseConsole()
EndIf 