I have an optimization problem of the form:


\begin{align}
&\text{maximize}\quad f(\mathbf{x}) = \dfrac{\sum\limits\_{n=1}^{N}x\_na\_n}{1+\sum\limits\_{n=1}^{N}x\_nb\_n}\\
& \text{subject to}\quad \sum\limits\_{n=1}^{N}x\_n\leqslant M,\\
& \quad\quad\quad\quad\quad\;\mathbf{x}=\left[x\_1,\ldots,x\_N\right]^\top\in\{0,1\}^N.
\end{align}
where $a\_n,b\_n$, for all $n$, $M$ and $N$ are the inputs of the problem.


It is a $0-1$ integer programming problem. Can we say that it is NP-hard? Or can you see a straightforward solution for it?


**EDIT:**


To me, the following algorithm looks like a good one but I cannot prove that it gives the optimal solution.



> 
> Algorithm:
> 
> 
> Step 1: Sort the list $(a\_1/b\_1,a\_2/b\_2,\ldots,a\_N/b\_N)$ and get the
>  index of the sorted list, i.e., a permutation $\sigma$ of
>  $(1,2,\ldots,N)$, $\sigma(1,2,\ldots,N)$.
> 
> 
> Step 2: Set $x\_n=0$ for all $n$.
> 
> 
> Step 3: Repeat until $\sum\_{n=1}^Nx\_n=M$
> 
> 
> Step 3.1: For $n$ in $\sigma(1,2,\ldots,N)$
> 
> 
> Step 3.2: Set $x\_n=1$
> 
> 
> 



Can we say that this problem is NP-hard?
Short answer: with negative $b\_i$'s, it's NP-hard, but otherwise it's polynomial time.


If you allow negative $b\_i$ then it is hard (set all the $a\_i=1$, so the goal is to get the chosen subset of $b\_i$'s to sum to a number close to but greater than $-1$ in order to make the denominator as small as possible — this is a subset sum problem.


If the $a\_i$'s and $b\_i$'s are all positive, you have a bicriterion matroid optimization problem (the condition that $\sum x\_i\le M$ is matroidal, and by bicriterion I mean taking a nonlinear combination of two linear functions). It is known that (under mild conditions on the nonlinear combination that hold for positive $b\_i$ but not negative ones) such problems can be solved in polynomial time by parametric techniques
(replace the objective function $\sum a\_i/(1+\sum b\_i)$ by the parametric function $\sum a\_i+\lambda(1+\sum b\_i)$, then vary $\lambda$ from $-\infty$ to $+\infty$ and keep track of the sequence of maximum weight bases you get — one of them will be the optimal value for the original objective function).


For more on parametric matroid optimization see my paper


Geometric lower bounds for parametric matroid optimization.
D. Eppstein.
Tech. Rep. 95-11, ICS, UCI, 1995.
27th ACM Symp. Theory of Computing, Las Vegas, 1995, pp. 662–671.
Disc. Comp. Geom. 20: 463–476, 1998.
<http://www.ics.uci.edu/~eppstein/pubs/Epp-DCG-98.pdf>


For more on the relation between parametric and bicriterion optimization (mostly not about matroids but with the same general principle) you can see another of my papers, more recent (although this connection is far from original to me):


The parametric closure problem.
D. Eppstein.
14th Algorithms and Data Structures Symp. (WADS 2015), Victoria, BC.
Springer, Lecture Notes in Comp. Sci. 9214 (2015), pp. 327–338.
<http://arxiv.org/abs/1504.04073>


The particular matroid involved in your question (a uniform matroid), when turned into a parametric optimization problem, has $O(n^{4/3})$ different changes of basis and they can be found in time proportional to that bound — see <https://en.wikipedia.org/wiki/K-set_(geometry)> for an equivalent problem in computational geometry.


