Knapsack-Greedy

Question

Answer 1

the correct answer is (b)

If you go through this heuristic approach you will get the value will be:

first, find value per wt--->

ob1: 3/7=0.42

ob2: 6/3=2

ob3: 8/5=1.6

ob4: 1/1=1

ob5: 2/4=0.5

ob6: 5/2=2.5

ob7: 7/6=1.16

Then arrange in descending order:

Ob6--> ob2--> ob3--> ob7--> ob4-->ob5-->ob1

now calculate the profit: (5+6+8+7+1+2=29)

The second question it is asking whether it is optimal or not:--->

to check this we need to try for normal 0/1 knapsack hit and trial to see whether it is possible to get more than 29 in 0/1 knapsack keeping maximum wt. of 24.

Ob3             5           8

Ob7             6           7

Ob2             3           6

Ob6             2           5

Ob1             7           3

Ob4             1           1

---

 total           24          30

---

As we can see we can get profit of 30 without using that heuristic approach in 0/1 knapsack. therefore the heuristic approach is definitely not optimal.

Comments

I can not understand why ob1 is not consider while calculating profit in heuristics approach?

I thought heuristics  approach  is same as fractional knapsack .is it so? Pls correct me.

Answer 2

i	1	2	3	4	5	6	7
v	3	6	8	1	2	5	7
w	7	3	5	1	4	2	6
v/w	0.4	2	1.6	1	0.5	2.5	1.16

After then arrange decresing order according to v/w:-

 T6----T2---T3----T7----T4----T5----T1

Profit : 5+6+8+7+1+2 = 29.

but using optimal substructure :

Profit : 5+6+8+7+1+2+3*(3/7) = 29+1.28 =30.28

hence Correct option is : B

Comments

A small confusion.....optimal structure which you have given is for fractional knapsack...and in question, it is asking for 0/1 knapsack. It is for sure that through 0/1 knapsack the answer would be 29 through this heuristic approach. but if you follow 0/1 knapsack without this heuristic approach you can achieve a value of 30 which is more optimal than this value. I think your answer is right but the explanation is wrong because to prove it not optimal you have used the fractional knapsack.