1
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ I suggest you try a few examples to see if this works. If all examples seem to work, try formulating a proof along the lines you saw in class. If the proof doesn't work, try designing a counterexample according to the step which seems to fail. $\endgroup$
    – Yuval Filmus
    Mar 26, 2014 at 3:39

3 Answers 3

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Ok thank you. I see after doing a few examples how I can use this. $\endgroup$
    – Ryan Smith
    Mar 26, 2014 at 3:45
  • $\begingroup$ You can skip the recursion/induction and just use an exchange argument: assume the optimal solution is strictly better than the greedy solution. If the optimal solution is not the same as the greedy, then there is some pair of items i,j with i<j in the ordering, where the optimal solution contains j but excludes i. Trade j for i, and show that this is always feasible and always at least as good. That contradicts the assumption that the optimal solution was better than the greedy one. $\endgroup$
    – DMGregory
    Mar 27, 2014 at 13:25
0
$\begingroup$

A simple solution would be like this:

  1. Generate solution using GREEDY technique.
  2. Calculate permutation of all possible answers, and see for the max profit satisfying weight constraint
  3. Now, you can check that your solution generated by GREEDY technique, and the permutation which yields max profit satisfying constraint is the same, then you can say that your algorithm is correct.
Improve this answer
$\endgroup$
-2
$\begingroup$

Let O be the optimal solution.

O = {o1, o2, o3 ..., oj}

Let G be our greedy solution.

G = {g1, g2, g3, ..., gk}

K = Initial Weight = Empty Knapsack

K = k - 0              //Initially

If g1 is in O then we are done.

But if g1 does not exist in O, then there might be another optimum solution.

O' = O - {g1}          Equation : 1
K' = K - {g1}          Equation : 2   //Which means w1(least weight)

If O' does not make an optimal solution then, our claim is wrong that g1 does not exist in O.

Therefore, 

O' = K'   // Since the optimum solution should have next weight possible
O' = K - {g1}          From Equation : 2
O' = O - {g1}          From Equation : 1
O - {g1} = K - {g1}    Equating

So, O = K

which proves that, The optimal solution after removing g1 from O' is still O.

Q.E.D

Improve this answer
$\endgroup$
5
  • $\begingroup$ Please check my solution and tell me if there are more suggestions. This is a similar proof as mentioned above. Just trying to use cs.stackexchange for good. $\endgroup$
    – technazi
    Oct 22, 2016 at 22:01
  • 1
    $\begingroup$ I don't understand what you're doing, here. You say that, if $g_1\notin O$, there is another optimal solution $O'=O\setminus\{g_1\}$. But, if $g_1\notin O$, then $O'$ isn't "another optimal solution" -- it's exactly the same solution as $O$. $\endgroup$
    – David Richerby
    Oct 22, 2016 at 22:54
  • $\begingroup$ Yes, It could be wrong or could be ambiguous. What i am trying to do is, State O as the optimum solution ; Check if g1 belongs to O ; If it doesn't then find another optimal solution from the existing optimal solution after removing g1. ; If it can not find the solution then my assumption is wrong. ; $\endgroup$
    – technazi
    Oct 22, 2016 at 22:57
  • $\begingroup$ I still don't understand. You talk about trying to remove $g_1$ from a solution that doesn't contain it. That doesn't change the solution. $\endgroup$
    – David Richerby
    Oct 22, 2016 at 23:00
  • $\begingroup$ please feel free to edit if this is potentially correct. $\endgroup$
    – technazi
    Oct 22, 2016 at 23:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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