in Algorithms edited by
3,491 views
7 votes
7 votes
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?
in Algorithms edited by
3.5k views

4 Comments

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
0
0

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

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

2 Answers

1 vote
1 vote

so difference=6-3=3

4 Comments

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

Better to go with 0/1 knapsack ...
0
0
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
0
0
what is the capacity of bag in your case?
0
0
0 votes
0 votes
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