Solving a knapsack-type problem

Question

I'd like a good way to solve an optimization problem I came across. It's a constrained knapsack problem: I want to find integers

$$1=a_1\le a_2\le\cdots\le a_t$$

$$a_1+a_2+\cdots+a_t=N$$

with $t$ as small as possible such that (with the $S_i\subseteq S={a_1,a_2,\ldots,a_t}$)

$$\sum_{e\in S_i}e=C_i$$

for a certain fixed collection $C_1 = 1, C_2 = 4,\ldots,C_k=N.$

What software exists for this sort of problem? I feel like writing my own program from the ground up would be the wrong approach.

I've been toying with COIN-OR and such but they seem set up for very different sorts of problems.

---

Ideally, I'd solve an even more complicated problem where $C_1$ and $C_k$ must match exactly and the other sums must be within a fixed range depending on the values of the neighboring C-values... but I don't imagine this is feasible?

Answer 1

This is not a variation of KNAPSACK since you can choose your weights.

From what you write, I assume that $C_1 < C_2 < \dots C_k$. Let me also explicitly state that you never demand the $S_i$ to be disjoint; the following approach would not work then.

Note first that you can safely drop the first restriction $1 = a_1 \leq \dots$. If you find feasible $a_i$ in any order, this can always be achieved by renaming.

Edit: The offered solution is suboptimal as has been pointed out in the comments.

Let $a_1 = 1$ and for $2 \leq i \leq k$ let $a_i = C_i - C_{i-1}$. These $a_i$ are an optimal solution since

• $C_i = \sum_{j=1}^i a_j$ obviously and
• $t=k$ is the minimum $t$ possible. Since all $C_i$ are pairwise different, we need at least one summand per $C_i$.

---

Edit: A new idea.

Start with $A = \{N\}$. For every $i$ from $N-1$ to $1$ do:

• If you can sum up $C_i$ with what is in $A$, continue with $i-1$.
• Let $m = \min \{ a \in A \mid a \geq C_i\}$
• If $m \neq C_i$, choose $p = \arg\min_r \{ |q - r| \mid r+q=m, r+a=C_i, a\in A_{< C_i}\cup\{0\} \}$ and set $A = (A \setminus \{m\}) \cup \{p, m-p\}$

The rather ugly argmin in words: For every $C_i$ take the smallest already chosen summand larger than $C_i$ and break it in as big chunks as possible while making sure that you can build $C_i$ with what you have. That should always work out, i.e. yield a solution.

I have no idea regarding optimality. For your example, the solution provided by you is found. Of course, I use SUBSET SUM, what is probably a bad idea. Doh.