Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 177

# DSA - Grand Test -Q19

Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 177

Consider the knapsack problem

N is the number of items

W is the maximum weight of the knapsack

P is the profit vector

w is the weight vector

N = 4, W = 11, P = ($\dpi{100} p_1,p_2,p_3,p_4$) = (50, 38, 10, 34) and w = ($\dpi{100} w_1, w_2, w_3,w_4$) = (8, 9, 2, 4)

The task is to pick a subset of these items such that their total weight is no more than 11 Kgs. If the items can be split, the maximum profit earned is $\dpi{100} split_p$ and if the items can't split, the maximum profit earned is $\dpi{100} 0/1_p$. What is the value of $\dpi{100} Split_p - 0/1_p$?

reshown Sep 10, 2020

+1 vote

Splitp is fractional knapsack. So, find profit/weight ratio. P/W ration of item 4 is maximum so take ALL the 4 units of item 4. Profit so far = 34

Now P/W ration of Item 1 is maximum. But we only have 7 units available in the bag and item 1 is 8 units so, take 7 units from item 1. So, profit = 34 + (50/8)*7 = 77.75

0/1 Knapsack will give maximum profit when we take item 1 and item 3. So, profit = 50+10 = 60

Final answer = 77.75 - 60 = 17.75

answered Sep 26, 2020 by (226,240 points)

Calculate profit/weight ratio for each

Take the one with max profit(for fractional knapsack)

we see that one with P4 has max P/w ratio

AS you need 11kg

multiply 11 by p/w ratio of item 4 you will get ${\color{Magenta} 93.5}$

0/1 knapsack

as you cannot divide

you need 11kg

only possible combination is 2+9 =11 as you cannot divide

2(5) + 9(4.22) = ${\color{Magenta} 47.98}$

the answer is${\color{Magenta} 93.5-47.98 = 45.52}$

answered Sep 26, 2020 by (11,240 points)
Check best answer. You have applied both incorrectly.
Oh god, I did a blunder. Thanks for correcting me, I forgot we only had 4kg of that item 4.
thanks.
:)