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 = () = (50, 38, 10, 34) and w = () = (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 and if the items can't split, the maximum profit earned is . What is the value of ? asked Aug 29, 2020
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

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) =  answered Sep 26, 2020 by (11,240 points)