# Minimize the sum of gaps

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?

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.
• Thanks. Calculating the minimum overall subsets, isn't it exponential? For $k=n$, it is $O(2^n)$?