Make your own free website on Tripod.com

Exercises 16.2-1:

Prove that the fractional knapsack problem has the greedy-choice property.

Answer:

The greedy-choice property: A globally optimal solution can be arrived at by making a locally optimal (greedy) choice. (Textbook page 380).

To prove the fractional knap sack problem, first we have to prove that the choice we have made that is going to be the best choice for that moment, and then that choice is the best choice for the problem.

Given that the knap sack capacity is 50lb and the optimal value for the bag has to be greater or equal $220.

Assume that items i1< i2< i3 having v1< v2< v3 are the value of each item, and the weight for each item as w1< w2< w3. We have c13 is the sub problem and let ck is the choice of items for the bag with the maximum value:

So that vn = max {vk : ck є c13}

The greedy-choice is selected base on the “dollar per pound” value for each item:

Item 1 = $60/10lb = 6

Item 2 = $100/20 = 5

Item 3 = $120/30 = 4.

To get the most dollar value out from this, the thief has to select the highest $/lb and has to use the knap sack to its maximum capacity - greedy-choice. There for we will have

 

First take item 1            Total Value = $60                    Total Weight = 10lb

Second take item 2       Total Value = $160                  Total Weight = 10 + 20 = 30lb

Takes 2/3 of item 3       Total Value = $240                  Total Weight = 10+20+2/3x30= 50lb

 

W = 10            W2 = 20                       W3 = 2/3x30 = 20

 

 


Item 1 = $60  Item 2 = $100         2/3 of item 3 = $80

The total value is greater $220 therefore this is a greedy-choice for this problem

 

Exercises 16.2-2:

Give a dynamic-programming solution to 0-1 knap sack problem that run in O(n W) time, where n is number of items and W is the maximum weight of items that the thief can put in his knapsack

Answer:

Let assume that: W is the maximum weight of the knapsack, n = i,k…j is the number of items the thief wants to take, item i has a set of attribute as vi and wi as value and weight respectively. The optimal solution is: He wants to take the as valuable a load as possible at most W pounds, therefore if we remove one item j from his load then the load is at most Wwj, and the number of item the thief takes n – 1.


 

The second step is to recursively define the value of an optimal solution. Let c[i,W] is value of the optimal solution for a sack of size W and items from 1 to i

                             0                                                                 if i = 0 or W = 0

            c[i,W] = {c[i-1, W]                                                 if wi > W

n

.

.

3

2

1

 
                             max (vi + c[i-1,W-wi], c[i-1,W])               if i > 0 and W ³ wi

 

 

 

 

 

 

1  2  3  …………..W Weight

 
 

 


From the table above for any value of n there is a value of weight W is associated to that, therefore the running time is O(n W)

 

Reference: http://www.cs.nyu.edu/courses/fall02/V22.0310-002/class-notes.html

                  And Katherine Macropol (assignment4)

 

 

 

Exercise 16.5-1:

 

ai

1

2

3

4

5

6

7

di

4

2

4

3

1

4

6

wi

10

20

30

40

50

60

70

Solve the instance of the scheduling problem given in the table above.

Answer:

Consideration points: Reschedule the tasks bases on two criterions “dead line” and “weight” for each task. Let sort the table on descending weight:

ai

7

6

5

4

3

2

1

di

6

4

1

3

4

2

4

wi

70

60

50

40

30

20

10

Ratio of w/d

11.6

15

50

13.3

7.5

6.6

2.5

 


 

Now re-sorted this table in combining the weight /dead-line (time) in order of earliest time first. If two tasks have a same deadline then whichever task has more weight will taking place first.

ai

5

4

6

3

7

2

1

di

1

3

4

4

6

2

4

wi

50

40

60

30

70

20

10

 

Therefore the answer is going to be as:

a5, a4, a6, a3, a7, a2, a1,

 

 

Problem 16-2: