Solving a knapsack-type problem 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?
 A: 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.
