How to solve the problem of knapsack 0-1 (its kind)?


Warning: count(): Parameter must be an array or an object that implements Countable in /home/styllloz/public_html/qa-theme/donut-theme/qa-donut-layer.php on line 274
0 like 0 dislike
9 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)?
by | 9 views

1 Answer

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.

Paraphrase task:

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

Related questions

0 like 0 dislike
2 answers
asked Jun 1, 2019 by keddad
0 like 0 dislike
6 answers
0 like 0 dislike
2 answers
asked Jun 4, 2019 by kkate4ka
0 like 0 dislike
2 answers
asked May 22, 2019 by ainilia
0 like 0 dislike
2 answers
110,608 questions
257,186 answers
0 comments
35,533 users