34 lines
1.2 KiB
Text
34 lines
1.2 KiB
Text
do -- Knapsack problem: Continuous - based on the Algol W sample, which is based on the EasyLang sample
|
|
|
|
local class Item
|
|
|
|
function __construct( name : string, weight : number, cost : number )
|
|
self.name = name
|
|
self.weight = weight
|
|
self.cost = cost
|
|
end
|
|
|
|
function price() : number
|
|
return self.cost / self.weight
|
|
end
|
|
|
|
end
|
|
|
|
local sackItems = { new Item( "beef", 3.8, 36 ), new Item( "pork", 5.4, 43 )
|
|
, new Item( "ham", 3.6, 90 ), new Item( "greaves", 2.4, 45 )
|
|
, new Item( "flitch", 4.0, 30 ), new Item( "brawn", 2.5, 56 )
|
|
, new Item( "welt", 3.7, 67 ), new Item( "salami", 3.0, 95 )
|
|
, new Item( "sausage", 5.9, 98 )
|
|
}
|
|
|
|
sackItems:sort( function( a, b ) return a:price() > b:price() end )
|
|
|
|
local maxWeight, i = 15, 0
|
|
while i <= # sackItems and maxWeight > 0 do
|
|
i += 1
|
|
local w = sackItems[ i ].weight
|
|
if w > maxWeight then w = maxWeight end
|
|
print( $"{w} kg {sackItems[ i ].name}" )
|
|
maxWeight -= w
|
|
end
|
|
end
|