Question

Suppose that in a 00-11 knapsack problem, the order of the items when sorted by increasing weight is the same as their order when sorted by decreasing value. Give an efficient algorithm to find an optimal solution to this variant of the knapsack problem, and argue that your algorithm is correct.

Answer 1

Answer:

Following are the response to the given question:

Explanation:

The glamorous objective is to examine the items (as being the most valuable and "cheapest" items are chosen) while no item is selectable - in other words, the loading can be reached.

Assume that such a strategy also isn't optimum, this is that there is the set of items not including one of the selfish strategy items (say, i-th item), but instead a heavy, less valuable item j, with j > i and is optimal.

As $W_i < w_j$, the i-th item may be substituted by the j-th item, as well as the overall load is still sustainable. Moreover, because $v_i>v_j$ and this strategy is better, our total profit has dropped. Contradiction.