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.

0 0

Δημιουργός

  • GeorgeV
  •  (Gold) 1123 points
  • 100% positive feedback
© 2024 CSOFT International, Ltd.