Home >  Term: unbounded knapsack problem
unbounded knapsack problem

Given types of items of different values and volumes, find the most valuable set of items that fit in a knapsack of fixed volume. The number of items of each type is unbounded. This is an NP-hard combinatorial optimization problem. Formal Definition: There is a knapsack of capacity c > 0 and N types of items. Each item of type t has value vt > 0 and weight wt > 0. Find the number nt > 0 of each type of item such that they fit, ∑t=1N ntwt ≤ c, and the total value, ∑t=1N ntvt, is maximized.

0 0

Creator

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