Correctness proof of greedy algorithm for 0-1 knapsack problem

Problem Detail: 

We have a 0-1 knapsack in which the increasing order of items by weight is the same as the decreasing order of items by value. Design a greedy algorithm and prove that the greedy choice guarantees an optimal solution.

Given the two orders I imagined that we could just choose the first k elements from either sequence and use them to fill knapsack until it was full. This would be similar to choosing the items with the greatest ratio of value to weight. But I don't think that is an optimal solution.

So what I need help with is whether or not this solution is optimal. And how would I prove the correctness of a greedy algorithm.

Asked By : Ryan Smith

Answered By : Yuval Filmus

Hint: Let $x$ be the item of smallest weight (and so of highest value). Take any solution which doesn't contain $x$. If there is room for $x$, add it to the solution. Otherwise, remove some element and add $x$ (why is that possible? does it necessarily improve the solution?). Conclude that the optimal solution always contains $x$. Apply this reasoning recursively to come up with a greedy algorithm.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/23058