50 lines
1.4 KiB
Plaintext
50 lines
1.4 KiB
Plaintext
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:
|
|
|
|
::::::{| style="text-align: left; width: 40%;" border="4" cellpadding="2" cellspacing="2"
|
|
|+ Table of potential knapsack items
|
|
|- style="background-color: rgb(255, 204, 255);"
|
|
! 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
|
|
|- style="background-color: rgb(255, 204, 255);"
|
|
| Knapsack || <=15 kg || ?
|
|
|}
|
|
|
|
|
|
<br>
|
|
;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]]
|
|
<br><br>
|
|
|
|
;See also:
|
|
* Wikipedia article: [[wp:Continuous_knapsack_problem|continuous knapsack]].
|
|
<br><br>
|
|
|