Monday, April 14, 2008

3.greedy knapsack theorem

3. If p1/w1 ≥ p2/w2 ≥ … ≥ pn/wn, then Greedy Knapsack generates an optimal solution to the given instance of the knapsack problem.
Proving technique:
Compare the greedy solution with any optimal solution. If the two
solutions differ, then find the first xi at which they differ.
Next, it is shown how to make the xi in the optimal solution equal to
that in the greedy solution without any loss in total value.
Repeated use of this transformation shows that the greedy solution
is optimal.

Proof: Let x=(x1,…,xn) be the solution generated by greedy knapsack. If all the xi =1, then clearly the solution is optimal. So, let j be the least index such that xj ≠1. From the algorithm it follows that xi=1 for 1<=ij.
if kif k=j, then since ∑ wixi=m and yi=xi for 1≤im.
if k>j, then ∑wiyi>m, and this is not possible.
Now suppose we increase yk to xk and decrease as many of (yk+1,…,yn) as necessary so that the total capacity used is still m. this results in a new solution z=(z1,…,zn) with zi=xi,1≤i
∑ pizi = ∑ piyi +(zk-yk)wk (pk/wk) - ∑ (yi-zi)wi (pi/wi)
1≤i≤n 1≤i≤n 1≤i≤n
≥ ∑ piyi + [(zk-yk)wk- ∑ (yi-zi)wi](pk/wk)
1≤i≤n 1≤i≤n

= ∑ piyi
1≤i≤n

If ∑ pizi >∑ piyi, then y could not have been an optimal solution .If these sums are equal. Then either z=x and x is optimal. Or z ≠ x.

No comments: