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

Dark Mode

3,491 views

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?

$\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?

0

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

0

1 vote

0