RosettaCodeData/Task/Knapsack-problem-0-1/00DESCRIPTION

{{omit from|GUISS}}

A tourist wants to make a good trip at the weekend with his friends.

They will go to the mountains to see the wonders of nature, so he needs to pack well for the trip.

He has a good knapsack for carrying things, but knows that he can carry a maximum of only 4kg in it,    and it will have to last the whole day.

He creates a list of what he wants to bring for the trip but the total weight of all items is too much.

He then decides to add columns to his initial list detailing their weights and a numerical value representing how important the item is for the trip.


Here is the list:
{| style="text-align: left; width: 80%;" border="4" cellpadding="2" cellspacing="2"
|+ Table of potential knapsack items
|- style="background-color: rgb(255, 204, 255);"
! item !! weight (dag) !! value
|-
| map || 9 || 150
|-
| compass || 13 || 35
|-
| water || 153 || 200
|-
| sandwich || 50 || 160
|-
| glucose || 15 || 60
|-
| tin || 68 || 45
|-
| banana || 27 || 60
|-
| apple || 39 || 40
|-
| cheese || 23 || 30
|-
| beer || 52 || 10
|-
| suntan cream || 11 || 70
|-
| camera || 32 || 30
|-
| T-shirt || 24 || 15
|-
| trousers || 48 || 10
|-
| umbrella || 73 || 40
|-
| waterproof trousers || 42 || 70
|-
| waterproof overclothes || 43 || 75
|-
| note-case || 22 || 80
|-
| sunglasses || 7 || 20
|-
| towel || 18 || 12
|-
| socks || 4 || 50
|-
| book || 30 || 10
|- style="background-color: rgb(255, 204, 255);"
| knapsack || ≤400 dag || ?
|}

<br>
The tourist can choose to take any combination of items from the list,
but only one of each item is available.

He may not cut or diminish the items, so he can only take whole units of any item.


;Task:
Show which items the tourist can carry in his knapsack so that their total weight does not
exceed 400 dag [4 kg], &nbsp; and their total value is maximized.

[dag = decagram = 10 grams]


;Related tasks:
* &nbsp; [[Knapsack problem/Bounded]]
* &nbsp; [[Knapsack problem/Unbounded]]
* &nbsp; [[Knapsack problem/Continuous]]
* &nbsp; [[A* search algorithm]]
<br><br>