There is one each of n kinds of dishes at a restaurant.
Accenture technical mcq question, verified with a worked answer. Free to practise - no sign-up.
There is one each of n kinds of dishes at a restaurant. Each dish has a price of c_i yen and the satisfaction points p_i (1 ≤ i ≤ n).
You have only W yen and want to maximize your total satisfaction points. Which is the correct algorithm to determine which dishes to order? Note that the variables in this problem, n, c_i, p_i, W, are positive integers.
Show answer & explanation
This is the fractional knapsack problem, which has a greedy optimal solution. Sorting by cost-effectiveness (satisfaction per yen) and greedily selecting items maximizes total satisfaction within the budget. Option A fails because high satisfaction at high cost leaves little budget for other items. Option B fails because low price doesn't correlate with good value. Option D is incorrect because C is provably optimal for this fractional optimization scenario.
Step-by-step Derivation:
This is a classic greedy algorithm problem. Counter-examples for A and B: suppose W=10 yen, with dishes (price, satisfaction): (3, 100), (4, 90), (5, 50). Algorithm A buys the 100-point dish first (leaving 7 yen), then the 50-point dish (total: 150). Algorithm B buys the 3-yen dish (100 points, 7 yen left), then the 4-yen dish (90 points, 3 yen left), total 190 points, but this is suboptimal. Algorithm C computes cost-effectiveness: 100/3≈33.3, 90/4=22.5, 50/5=10. It buys in order (3,100), (4,90), (5,50) up to budget, achieving optimal value. The greedy choice of maximum value-per-unit-cost at each step provably maximizes total satisfaction.