- #1

Pereskia

- 15

- 2

(Not sure which forum to pick for this question. This looked like the best one. I apologies if it is not)

I have a number of functions (say m functions) with integer domain. All functions are increasing. (Increasing in the sense not decreasing, $f(n+1) \ge f(n)$.) I want an algorithm to find $n_i$ for $1 \le i \le m$ such that $\sum_i^m n_i \le N$ that maximizes $\sum_i^m f(n_i)$.

$m$ is usually small (2 or 3) but can be larger as well and $m$ = 2 can be solved reasonably fast by exhaustive search, $m\ge3$ takes more time. Typically $N\approx 500$.

Is there any known algorithm?

Regards

David