1
$\begingroup$

In knapsack problem, we have some items with some values and weights. We also have a knapsack with a specific capacity, and we intend to fill the knapsack with these items. The main objective of this problem is to maximize the value of items in the knapsack.

Knapsack can contain maximum 11 kg items

item1: value(1) weight(1 kg)

item2: value(6) weight(2 kg)

item3: value(18) weight(5 kg)

item4: value(22) weight(6 kg)

item5: value(28) weight(7 kg)

Are the items also sorted by their weights when we sort them by their values ?

In other words, are the weights parallel with the values ?

For example, can the item2 have a value 20 but its weight is equal to 2 kg ?

$\endgroup$
1
$\begingroup$

The weights and values can be arbitrary. In particular, if you sort the items by their weight, then they need not be sorted by their value.

More generally, if you look at a formal definition of the Knapsack problem, you will see that nothing is mentioned about the possible weights and values of the items (beyond their being positive integers). Every instance which conforms to the definition is valid.

In other words, you should be able to answer such questions by looking at the formal definition of the problem. There is no hidden information which can only be obtained by asking questions on forums. Indeed, it is exactly the opposite — the problem statement defines the problem completely.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.