1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Thanks. Calculating the minimum overall subsets, isn't it exponential? For $k=n$, it is $O(2^n)$? $\endgroup$
    – zdm
    Apr 10 '20 at 20:41
  • $\begingroup$ Are you familiar with dynamic programming? $\endgroup$ Apr 10 '20 at 21:15
  • $\begingroup$ Not really. I know some basics. Do you mean dynamic programming will find the minimum without looking at all subsets? $\endgroup$
    – zdm
    Apr 10 '20 at 21:45
  • $\begingroup$ Dynamic programming can solve it in polynomial time. After you familiarize yourself with the technique, you should be able to use my outline to come up with such an algorithm. Unfortunately I cannot help any further. Dynamic programming is a standard technique, and there are many places where you can read about it. $\endgroup$ Apr 10 '20 at 21:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.