Algorithms

Question 236

Which of the following greedy strategies gives the optimal solution for the following 0-1 knapsack problem?

w=30, w1=10, p1=11, w2=15, p2=12, w3=20, p3=24, w4=25, p4=25

A	Largest profit per unit weight first
B	Largest profit first
C	Lightest item first
D	Heaviest item first

Algorithms0/1-Knapsack-and-fractional-knapsackJT(IT) 2018 PART-B Computer Science

Question 236 Explanation:

Note: Even though they are asking 0/1 knapsack. We are always takes first profit/weight first.
→ W=30, we can exceed weight and we can’t take fractions of weight.
→ According to profit/weight, W3 having more profit. And W1 having more profit.
→ 0/1 knapsack optimal solution = 24+11 = 35

Correct Answer: A

Question 236 Explanation:

Note: Even though they are asking 0/1 knapsack. We are always takes first profit/weight first.
→ W=30, we can exceed weight and we can’t take fractions of weight.
→ According to profit/weight, W3 having more profit. And W1 having more profit.
→ 0/1 knapsack optimal solution = 24+11 = 35

Theory-of-Computation

UGC NET CS 2010 Dec-Paper-2

Theory-of-Computation

UGC NET CS 2010 Dec-Paper-2

Algorithms

Shubham vyas