Minimize the sum of gaps

Question

I have a set of $n$ objects $\{1,2,\ldots,n\}$ where object $i$ has weight $w(i)$ and we have a capacity $W$. I would like to pick a subset $S=\{a_1,\ldots,a_m\}\subseteq \{1,2,\ldots,n\}$ of the objects in order to minimize $$\sum_{j=0}^m(a_{j+1}-a_{j}-1),$$ (assuming that $a_0=0$ and $a_{m+1}=n+1$) while respecting the capacity, i.e., $$\sum_{j=1}^mw(a_j)\leq W.$$

The objective is like the sum of gaps between chosen objects.

Is this problem NP-hard or can we find a polynomial time algorithm?

Answer 1

For every $k$ and $\sigma$, let $A(k,\sigma)$ be the minimum of $\sum_{j=1}^m w(a_j)$ over all subsets $a_1,\ldots,a_m$ of $\{1,\ldots,k\}$ containing $k$ such that $\sum_{j=0}^m (a_{j+1} - a_j - 1) = \sigma$; note that there are $O(n)$ choices for each of $k$ and $\sigma$. You can compute $A(k,\sigma)$ for all $k,\sigma$ using dynamic programming, and use it to solve your problem in polytime.