In today's post
we look at some more greedy algorithms again based on mecr.org lectures The knapsack problem is a well known problem to discuss greedy algorithm. This problem is stated this way there are bags of chemicals. Each bag has a specific weight and price. The goal is to fill the knapsack so as to maximize the price. Weights are measured in kilo grams and price is measured on dollars if you have more chemicals that can fit in a knapsack you have to make choices .
We do this by arranging the bags in order of priority. We measure this as price over weight ratio we fill the knapsack my picking items in increasing order of this price to weight ratio. There may be a point when we cannot add a chemical without splitting it into a smaller portion all the chemicals beyond that one cannot be considered since our knapsack is full
I wanted to finish this post but got sidetracked. I will do this now
We have taken items by unit cost. We go one item by item in that order until we fill each item
We sorted our bags by unit cost. i.e P1/W1, P2/W2, ... PN/WN in that order. Then we picked up as much of the first bag as possible, typically all of it it and continue down the line. We stop at some j and ignore th rest j+1 to N bags.
That is we have a sequence of 1 for all the bags we selected and a sequence of zero for all the bags we ignored.
We now show the proof of optimality We use a standard technique to transform any optimal solution to a greedy one
We begin with an optimal solution. We show that at each item we add an optimal step.
Let y = y1, y2, ... yN is Optimal.
The Greedy x = x1, x2, ... xyi, Xn be the greedy choices
y is not equal to x.
Let K be the smallest index such that yk is not equal to xk
The claim is yk < xk
x1, x2, ... xj-1 xj xj+1 .. xN is the sequence of choices
Let xi = 1
if yk != xk => yk < 1 => yk < xk
for xj, we know xj is the maximum, then the above statement mean yj > xj which is infeasible.
So we have yj < xj
for xj+ 1 to xN, we trivially show that yk > xk is not possible. upto j y and x agree. after that x is 0. Now yhas also filled up the knapsack so y is also zero after that point.
Our goal is to transform y into x.
We have yk < xk. Increase yk to be xk. Reduce yk+1 .. yN to restore feasibility.
The total weight comes back to 1
y is new feasible solution z = z1, z2, ... zn
for 1 < =i <= k, xi = zi
after k if we increase the weight wk (xk - yk ) to sum i = K + 1 to N wi(yi -zi)
we look at some more greedy algorithms again based on mecr.org lectures The knapsack problem is a well known problem to discuss greedy algorithm. This problem is stated this way there are bags of chemicals. Each bag has a specific weight and price. The goal is to fill the knapsack so as to maximize the price. Weights are measured in kilo grams and price is measured on dollars if you have more chemicals that can fit in a knapsack you have to make choices .
We do this by arranging the bags in order of priority. We measure this as price over weight ratio we fill the knapsack my picking items in increasing order of this price to weight ratio. There may be a point when we cannot add a chemical without splitting it into a smaller portion all the chemicals beyond that one cannot be considered since our knapsack is full
I wanted to finish this post but got sidetracked. I will do this now
We have taken items by unit cost. We go one item by item in that order until we fill each item
We sorted our bags by unit cost. i.e P1/W1, P2/W2, ... PN/WN in that order. Then we picked up as much of the first bag as possible, typically all of it it and continue down the line. We stop at some j and ignore th rest j+1 to N bags.
That is we have a sequence of 1 for all the bags we selected and a sequence of zero for all the bags we ignored.
We now show the proof of optimality We use a standard technique to transform any optimal solution to a greedy one
We begin with an optimal solution. We show that at each item we add an optimal step.
Let y = y1, y2, ... yN is Optimal.
The Greedy x = x1, x2, ... xyi, Xn be the greedy choices
y is not equal to x.
Let K be the smallest index such that yk is not equal to xk
The claim is yk < xk
x1, x2, ... xj-1 xj xj+1 .. xN is the sequence of choices
Let xi = 1
if yk != xk => yk < 1 => yk < xk
for xj, we know xj is the maximum, then the above statement mean yj > xj which is infeasible.
So we have yj < xj
for xj+ 1 to xN, we trivially show that yk > xk is not possible. upto j y and x agree. after that x is 0. Now yhas also filled up the knapsack so y is also zero after that point.
Our goal is to transform y into x.
We have yk < xk. Increase yk to be xk. Reduce yk+1 .. yN to restore feasibility.
The total weight comes back to 1
y is new feasible solution z = z1, z2, ... zn
for 1 < =i <= k, xi = zi
after k if we increase the weight wk (xk - yk ) to sum i = K + 1 to N wi(yi -zi)
No comments:
Post a Comment