Home > Term: knapsack problem
knapsack problem
Given items of different values and volumes, find the most valuable set of items that fit in a knapsack of fixed volume. Formal Definition: There is a knapsack of capacity c > 0 and N items. Each item has value vi > 0 and weight wi > 0. Find the selection of items (δi = 1 if selected, 0 if not) that fit, ∑i=1N δiwi ≤ c, and the total value, ∑i=1N δivi, is maximized.
- Μέρος του λόγου: noun
- Κλάδος/Τομέας: Υπολογιστές
- Category: Αλγόριθμοι & δομές
- Government Agency: NIST
0
Δημιουργός
- GeorgeV
- 100% positive feedback