

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.


#define PesoMax  15.0
Type Knapsack
    articulo As String*7
    peso As Double
    precio As Double
End Type
'build item list
Dim item(1 To 9) As Knapsack => { _
("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)}
 
Dim As Boolean Roba(Ubound(item))
Dim As Double PrecioXPeso(Ubound(item))
Dim As Integer i, MejorArticulo
Dim As Double Mejor, PesoArtic, TotalPeso = 0, TPeso = 0, TPrecio = 0, temp
 
For i = 1 To Ubound(item)
    PrecioXPeso(i) = item(i).precio / item(i).peso
    Roba(i) = False
Next i
 
Print "You can carry the following materials in the knapsack: "
Do
    Mejor = 0
    For i = 1 To Ubound(item)
        If Not Roba(i) And PrecioXPeso(i) > Mejor Then
            Mejor = PrecioXPeso(i)
            MejorArticulo = i
        End If
    Next i
    Roba(MejorArticulo) = True             'take item
    PesoArtic = item(MejorArticulo).peso   'get its weight
    TotalPeso += PesoArtic                 'add to total weight
    If TotalPeso > PesoMax Then            'if total is too much, reduce
        PesoArtic -= TotalPeso - PesoMax   'item weight by amount it's over
    End If
    Print Using "##.# kg of "; PesoArtic;  'show weight and item
    TPeso += PesoArtic
    Print item(MejorArticulo).articulo;
    temp = PesoArtic * item(MejorArticulo).precio / item(MejorArticulo).peso
    TPrecio += temp
    Print Chr(9); Using "(Value = ##.###)"; temp
Loop Until TotalPeso >= PesoMax            'all we can steal
 
Print !"\nMaximal weight:"; PesoMax;  " kg"
Print Using "Total weight:  ###.## kg"; TPeso
Print Using "Total value:   ###.##"; TPrecio
Sleep