Greedy Method

Input : X = {x₁, x₂, . . ., x_n}

Solution(s) (S) are contained in X (some combination)
S X ;
2^|x| -possible subsets of X

Feasible solution (FS): FS 2^|x| combinations. Feasible if satisfies constraints.

S FS <--> f(S) < 0

We need to find a feasible solution that either maximizes or minimizes a given objective function. A feasible solution that does this is called an optimal solution

Optimal solution: S FS such that g(S) is optimum

Method of solution:

1. Order inputs according to some selection procedure
2. Select next input
3. If input can be included in solution subject to feasibility then do so
4. Go to step 2

i=1 to n   x_ip_i is maximum (profit maximized)

Ex: n = 3       W = (18, 15, 10)       P = (25, 24, 15),       M = 20

X	xiwi	xipi
1/2, 1/3, 1/4	16.5	24.25
0, 2/3, 1	20	31
0, 1, 1/2	20	31.5

We could order according to decreasing profit (pick the highest profit first):

P:	10	5	1	M = 10
W:	100	10	1
X:	1/10	0	0	xipi = 1
but
X:	0	1	0	xipi = 5

But chosing the highest value first does not always give us optimal.

Order according to increasing weight:

W:	1	10	100	M = 1
P:	1	100	1000
X:	1	0	0	xipi = 1
but
X:	0	1/10	0	xipi = 10

But chosing greedily here does not always give us optimal either.

Selection based on profit alone or weight alone will not lead to optimal solution.
Consider a ratio of profit to weight.

Solution:
If for i=1 to n w_i < M       then x_i = 1 for all 1< i <n is a "trivial" optimal solution.
This means we could put everything in the sack - boring.
Otherwise, assume any optimal solution must fill knapsack to capacity according to the following algorithm

Algorithm sack (P, W, M, X, n)
{
sort p_i/w_i in decreasing order
// ie.      p₁/w₁ > p₂/w₂ >       . . .       > p_n/w_n
for i = 1 to n       while M > 0 do
      if w_i < M      
then x_i = 1
else x_i = M/w_i
      M = M - x_i w_i
}

Proof: by contradiction and transformation

X (vector of x_i's): Solution obtained by algorithm

Suppose X not optimal

Let Y be optimal
Transform Y to X (transform Y to some Z, and show that that Z must be X)
without changing value of optimizing function, thus showing that X is optimal as well.

See also page 201 (read)

If x_i = 1, 1 < i < n, then X is optimal.
Let j be least index such that x_j < 1.
ie. x_i = 1, 1 < i < j, x_j < 1

From alg. it follows that x_i = 0, j < i < n.

x1	x2	...	xj-1	xj	xj+1	...	xn
1	1	...	1	< 1	0	...	0

If X not optimal, let Y be optimal

i=1 to n p_iy_i       >       i=1 to n p_ix_i

w.l.o.g. i=1 to n y_iw_i = M

Let k be the least index such that x_k != y_k (must be at least one)
Remember, j is the first index that is not a value of 1 for X.

Claim:      y_k      <       x_k
prove claim by looking at the only three cases possible:

• case 1: k < j
  Then x_k = 1      ;       But x_k != y_k       so 0 < y_k < 1
  ==> y_k < x_k = 1

• case 2: k = j
  Since i=1 to n w_ix_i = M       ;       y_i = x_i       for all i, 1 < i < j,
  If y_k > x_k then i=1 to n w_iy_i > M.
  Therefore y_k < x_k

• case 3: k > j
  If y_k > x_k then i=1 to n w_iy_i > M.
  This is not possible, therefore y_k < x_k

Y	y1	...	yk-1	yk	yk+1	...	yn
	||	...	||	^	V/	...	V/
	z1	...	zk-1	zk	zk+1	...	zn
	||	...	||	||		...
X	x1	...	xk-1	xk	xk+1	...	xn

increase in weight = w_k (z_k - y_k)
decrease in weight = i=k+1 to n (y_i - z_i)w_i

weight must stay the same so,

i=k+1 to n (y_i - z_i)w_i = (z_k - y_k)w_k

increase in profit = (z_k - y_k) p_k
decrease in profit = i=k+1 to n (y_i - z_i)p_i

If increase > decrease
then Z is optimal as well.

Repeat: Need to show increase > decrease which is:

(z_k - y_k) p_k       >?       i=k+1 to n (y_i - z_i)p_i

OR (take each side and divide and multipy by the same term - will need this form)

(z_k - y_k) p_k/w_k * w_k       >?       i=k+1 to n (y_i - z_i)p_i/w_i * w_i

We know the following (and it will be useful):
             p_k/w_k     >     p_i/w_i , k < i < n, (ordered that way)
          multiply both sides by the same terms
            i=k+1 to n (y_i - z_i)*p_k/w_k * w_i     >    i=k+1 to n (y_i - z_i)*p_i/w_i * w_i

OK, we now need to show

(z_k - y_k) p_k/w_k * w_k       >?       i=k+1 to n (y_i - z_i)p_k/w_k * w_i

(z_k - y_k)w_k * p_k/w_k      >?       p_k/w_k i=k+1 to n (y_i - z_i)w_i

divide both sides by p_k/w_k      note that what is left is the relation about weights that had to stay the same

Therefore profit increase      >       decrease.       hint on what just happened there

Transition Y --> Z does not decrease profit

If profit increases, Y not optimal
Therefore Z is optimal.

Repeat transformations until Y --> Z --> . . . --> X without change in profit.

Therefore X is optimal.

1. General
2. Spanning trees
3. Single source shortest path