Knapsack problem/Continuous: Difference between revisions
no edit summary
(+ second D entry) |
No edit summary |
||
Line 1,684:
'salami ': 3.000000e+00,
'welt ': 3.500000e+00></pre>
=={{header|XPL0}}==
<lang XPL0>int Name, Price, I, BestItem;
real Weight, Best, ItemWt, TotalWt;
def Items = 9;
real PricePerWt(Items);
int Taken(Items);
include c:\cxpl\codes;
[Name:= ["beef","pork","ham","greaves","flitch","brawn","welt","salami","sausage"];
Weight:= [ 3.8, 5.4, 3.6, 2.4, 4.0, 2.5, 3.7, 3.0, 5.9];
Price:= [ 36, 43, 90, 45, 30, 56, 67, 95, 98];
for I:= 0 to Items-1 do
[PricePerWt(I):= float(Price(I)) / Weight(I);
Taken(I):= false;
];
Format(2,1);
TotalWt:= 0.0;
repeat Best:= 0.0;
for I:= 0 to Items-1 do
if not Taken(I) and PricePerWt(I) > Best then
[Best:= PricePerWt(I); BestItem:= I];
Taken(BestItem):= true; \take item
ItemWt:= Weight(BestItem); \get its weight
TotalWt:= TotalWt + ItemWt; \add to total weight
if TotalWt > 15.0 then \if total is too much, reduce
ItemWt:= ItemWt - (TotalWt-15.0); \item weight by amount it's over
RlOut(0, ItemWt); Text(0, " kg of "); \show weight and item
Text(0, Name(BestItem)); CrLf(0);
until TotalWt >= 15.0; \all we can steal
]</lang>
Output:
<pre>
3.0 kg of salami
3.6 kg of ham
2.5 kg of brawn
2.4 kg of greaves
3.5 kg of welt
</pre>
| |||