3,491 views
The difference between maximum possible profit for $0/1$ Knapsack and fractional Knapsack problem with capacity $(W)=20$.

$\begin{array}{|c|c|c|c|c|c|} \hline \text{Item} & a & b & c & d & e & f & g & h & i & j\\ \hline \text{Weight} &3 & 5 & 2 & 1 & 12 & 10 & 9 & 9 & 4 &1 \\ \hline\text{Profit} & 7 & 10 & 3 & 3 & 26 & 19 & 18 & 17 & 5 & 4 \\\hline \end{array}$

For 0/1 knapsack, we have to make the whole table or there is any direct method to this?

the trick is you should find the P/W ration like greedy knapsack and short them in decreasing order then place it accordingly then you can fill up till the knapsack capacity end

@Hemanth_13 that is the reason that the chances of this type of question coming in gate will be slim

In 0/1 knapsack i got 39 how you got 39 pz elaborate

so difference=6-3=3

by

edited
Does this method work for all cases?
I think not ! You have to check last 2 to 3 selection !

Better to go with 0/1 knapsack ...
this wont work on all the problem for example pi={10,12,28} and wi={1,2,4} then your approach for solving 0/1 knapsack won't work. The question is how to solved 0/1 without drawing whole table on paper as it can be seen from given problem table size would be of 200 cells
what is the capacity of bag in your case?
Ans :- 3.4

Common part for both (j+d+e)

For fractional knap sack, common part + 6/10 * f

For 0/1 knapsack , common part + c + i

X = difference betn profits = 3.4

1
563 views
1 vote