Q5 /5 You are the manager of a mixed juice shop.
Accenture technical mcq question, verified with a worked answer. Free to practise - no sign-up.
You are the manager of a mixed juice shop. You can make m kinds of mixed juice by mixing n kinds of fruit juice. To make mixed juice j (1 ≤ j ≤ m), you have to mix fruit juices 1, 2, ..., n in a ratio of c₁ⱼ : c₂ⱼ : ... : cₙⱼ. You have Lᵢ liters of fruit juice i now (1 ≤ i ≤ n). The price of a mixed juice j is pⱼ yen per liter.
You want to maximize the combined total price of all of the mixed juice you can make using only the fruit juices you have now. Which of the following statements is true about the algorithm that should be used to solve this kind of problem, assuming it runs on a single processor?
Show answer & explanation
This is a linear programming problem: maximize Σⱼ pⱼ · xⱼ subject to Σⱼ (cᵢⱼ / Σₖ cₖⱼ) · xⱼ ≤ Lᵢ for each ingredient i, where xⱼ is liters of juice j produced. Linear programs are solvable in polynomial time (e.g., ellipsoid method, interior-point methods), but a greedy algorithm does not guarantee optimality. The problem is not NP-hard because it's continuous and convex, so option C is false. The O(n+m) complexity claim in A is also false.
Step-by-step Derivation:
Formulation: Let xⱼ be liters of mixed juice j produced. For juice j with ratios c₁ⱼ : c₂ⱼ : ... : cₙⱼ, the total ratio sum is Σₖ cₖⱼ. To produce xⱼ liters requires (cᵢⱼ / Σₖ cₖⱼ) · xⱼ liters of ingredient i. Constraint: Σⱼ (cᵢⱼ / Σₖ cₖⱼ) · xⱼ ≤ Lᵢ for each i ∈ [1, n]. Objective: maximize Σⱼ pⱼ · xⱼ. This is a linear program with n + m variables (x₁, ..., xₘ plus slack variables) and n constraints. Standard LP solvers run in polynomial time O((n+m)³·L) where L is bit complexity. A greedy approach (e.g., always maximize the highest-price juice first) fails because the constraints couple all juices; one juice's production limits others. Therefore, B is correct: polynomial solvability but not O(n), and not NP-hard.