# Tag Info

So if you are not updating the #satisfied/cost ratio after every selection, this algorithm won't perform well. Let $n$ be the number of people and $m$ the number of meals. We denote the cost of meal $i$ by $w_i$. Let's say people $1...n-1$ are all satisfied by meals $1...m-1$ which all have the same cost, but person $n$ will only eat meal $m$. If the cost ...
The problem is equivalent to that of finding $$\begin{array}{l} \min x_1 + x_2 + x_3 \quad \mbox{s.t.} \\ x_1 (A-1) + x_2 (B-1) + x_3 (C-1) = N - K \\ x_1,x_2,x_3 \in \mathbb{N} \end{array}$$ Assuming $A,B,C \ge 1$, this can be solved in $O(N-K)$ time (for $N-K>0$) via dynamic programming and, depending on the values of $A$, $B$, and $C$, the greedy ...