0/1 knapsack

Question

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?

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

---

@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

Answer 1

so difference=6-3=3

Comments

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?

Answer 2

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