New answers tagged greedy-algorithms
1
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 ...
0
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 ...
Top 50 recent answers are included
