# 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?

-
For an idea of the size of the problem, t = 10 is almost certainly infeasible and t = 250 is feasible. k = 255 and N is around 50,000. A good solution would be fine -- I don't need to find the best possible. – Charles Jan 14 '11 at 15:54
Have you thought about looking into lattice reduction algorithms (i.e. LLL or PSLQ)? I believe they've had some success with problems similar to this (googling found this, though I don't know how useful it will be). – user4143 Jan 14 '11 at 20:10
@user4143: Would you add that as an answer? – Charles Jan 21 '11 at 16:43

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.

-
That's not optimal. Suppose the C are (1, 2, 3, 4, 5, 6, 7, 28). Your solution gives (1, 1, 1, 1, 1, 1, 1, 21), a total of 8 members. But (1, 2, 4, 21) also works and is much smaller. – Charles Jan 14 '11 at 19:59
By the way, the S_i cannot be disjoint (for t > 1) since S_t = S contains all the weights. – Charles Jan 14 '11 at 20:00
Why would you have $S_t$? I though you have $S_1, \dots S_k$. Anyway, please consider my (not very fruitful) edit. – Raphael Jan 14 '11 at 23:57
That's the greedy algorithm -- reasonable, though certainly not optimal. – Charles Jan 15 '11 at 19:44