Can we say that this problem is NP-hard? 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$

 A: 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.
