• Register
    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 580

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
  • Questions
    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 580
  • Unanswered
    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 580
  • Tags
    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 580
  • Categories
    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 580
  • Users
    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 580
  • Exams Taken
    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 580
  • Exam List
    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 580

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

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

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

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

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

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
+2 votes

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 = (p_1,p_2,p_3,p_4) = (50, 38, 10, 34) and w = (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 split_p and if the items can't split, the maximum profit earned is 0/1_p. What is the value of Split_p - 0/1_p?

asked Aug 29, 2020 by gbeditor-2 (72,840 points)
reshown Sep 10, 2020 by gbeditor-2

2 Answers

+1 vote
 
Best answer

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 deepak-gatebook (226,240 points)
0 votes

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

add p/w ratio of both

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 tsshashankrustagi (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.
:)
Answer:

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

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

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