0 like 0 dislike
13 views
Let there be a set of objects, each of which has two parameters, weight and value. The backpack also has a certain capacity. The challenge was to pack a bag with a maximum value of objects inside, while respecting the constraint of a backpack on the total weight. All items are unique.

How to solve the task about a backpack, if the backpack is limited not only by capacity but also by the number of items that can be put (and the number of items must be equal to this limit, no more and no less)?
| 13 views

0 like 0 dislike
I understand that Your problem is that the number of items must be strictly equal to limit? In the standard task limitations on the number of selected items no.

Let's say you have N items, a backpack should be stocked with items, and To<=N. you Need to choose a complete set, the total weight does not exceed the maximum allowed and total value of items was highest.

Offering You a solution "in a forehead":

Create a list of all combinations of K over N (for combinatorial computation, there are special libraries for most programming languages). For each combination, calculate its weight and remove those combinations which exceed the weight limit. Ostavshiesya combination autocontinuity in descending order the values and take the top.
by

0 like 0 dislike