# 0-1 knapsack like - the set of all non-contained affordable binary selections

This is my first question here, so please go easy on me :)

The following problem is – I think - similar to the 0-1 knapsack problem. It's simplified somehow in that each item has only a cost (weight), not a weight/value pair. However, what I need is not one optimal solution but the set of all "maximal" solutions.

Problem Definition:

• There is a set of items, each with a cost.
• A selection contains one or more items.
• Each item can appear at most once in each selection (i.e. 0-1)
• A selection is affordable if the total cost of the items in the selection is not more than a constant budget.
• The amount of budget not used in a selection is waste.

For a given budget, items and costs, find all affordable selections which are not subsets of other affordable selections.

Example:

• Suppose there are four items with costs of 1, 2, 3, and 5.
• Suppose your budget is 7
• The set of affordable selections is {{1,5}, {1,2,3} and {2,5}}
• The corresponding wastes are 1, 1 and zero.

So, my question is: Can this be done without brute force? How would you solve this?

P.S. My real-life problem contains about 40 items.

Edit: It always pays to provide the big picture ;) This problem is one stage in a complex one I have to solve in a few days with minimal qualifications :(. There is about to happen a selection game, in which each contender will select one item in her turn according to her budget (if your budget is large enough, you'll take part in more than one turn). Budget is one constraint, minimizing the waste is another, but additionally each item has other attributes so a contender may prefer one selection over another, even if both selections are affordable and even is no budget is wasted.

The selection will be real-time, so my thinking was to

1. write software that would find all affordable solutions, then
2. group the affordable selections according to the attributes and identify preferred ones
3. find which selections are robust against other players moves (i.e. can't be easily "blocked")
4. provide some time of assistance during the selection process, to zero-in on the moves that are still open, according to other players moves, which would lead to a preferred affordable selection.
-
If you have only about 40 items, why not use brute force? With just a few optimizations, it's going to fast enough. – ShreevatsaR Nov 13 '12 at 17:34
2 to the power of 40 iterations/space? – Avi Nov 13 '12 at 17:35
With some pruning it's going to be much faster than that on real data; and in any case even enumerating all $2^{40}$ cases at about $10^9$ per second (say) is less than 20 minutes. Next question: how big are the actual costs? If you have a bound on the largest cost (or equivalently, on the sum of the costs, or even just on your budget), then a dynamic programming approach should work. – ShreevatsaR Nov 13 '12 at 17:38
Estimations for the costs of the items are between 40 and 200, and the budget is 500 (all numbers are, for now, guesstimates) – Avi Nov 13 '12 at 17:44
Oh great. With a budget of about 500 (and assuming the costs are nonnegative integers), there is an $O(Bn)$ algorithm (here, $(500)(40)\approx20000$) to find (say) all achievable costs below your budget. The enumeration makes it slow, though. Are you sure you need all the maximal affordable selections? E.g., with every item having cost $25$, and a budget of $500$, your list is all sets of size $20$, so there are ${40 \choose 20}\approx\frac{2^{40}}{8}$ selections that the output will have, so just output will take a lot of time. – ShreevatsaR Nov 13 '12 at 17:58

It sounds to me like you're actually solving the wrong problem. As I understand it, you're playing a game where each player gets to make moves in turn. A move consists of taking an item from a pool of available items. Each item has an associated cost, and a player can only take an item from the pool if they have enough budget to do so and no player has previously taken that item from the pool. You want an optimal strategy for that game.

Let's look at some sizes here:

• There are ~40 available items, so the number of possible subsets is $2^{40} \approx 10^{12}$.
• The game tree has size $40! \approx 10^{48}$

Both of these numbers are too big to reasonably store and do any useful computation with, and there's no real guarantee that precomputing all the maximal subsets is actually going to be useful in choosing a strategy. Also note that the problem of finding a single optimal assignment is NP-complete (although that's not too bad in your case since you only have 40 items), so the problem of enumerating all the optimal solutions is going to be fairly nasty even ignoring the space complexity (although the space complexity is the real problem here).

Instead I'd recommend using a graph search algorithm like alpha-beta pruning or A*-search on the game tree. At each branch point of the tree, you can use the as a search heuristic the maximum final score that the current player could make given all the items left in the pool, their current items and their current budget. Finding that score is still NP-complete (so you're gonna need to use an SMT solver to find it), so it might actually be too slow as a search heuristic, but then again it might not! In any case, it's likely to be much faster than trying to precompute all the optimal sets and is almost certain to end up producing a better strategy.

Alpha-Beta pruning

A* search

Using an SMT solver to solve the knapsack problem

-

Here's my take:

Let's say the items are in a sequence a1, ... , an, where each item has a cost of c1, ... cn.

Define the operation X on an item and a set of sequences of items as the set of sequences where item is concatenated to each of the sequences.

Define the operation B on an item and a sequence where B returns a set of item sequences as:

B(budget, ai) =
If ai+1 exists
Start
if budget > ci
return {ai X B(budget - ci, ai+1)} U B(budget, ai+1)
else if budget = ci
return {"ai"} U B(budget, ai+1)
else return B(budget, ai+1)
End
Else if budget >= ci
return {"ai"}
Else
return {}


The idea of {ai X B(budget - ci, ai+1)} U B(budget, ai+1) is that we can either take ai or we can leave it alone. If we take it, we pay the cost but get to concatenate ai to all the items in the result set of ai+1. If we don't use it, we don't pay the cost so we can get a richer result set of ai+1 obtained using a non-diminished budget.

In the example specified above we have the four items a5, a3, a2 and a1, with their corresponding costs c5 = 5, c3 = 3, c2 = 2 and c1 = 1. We also have a budget of 7. (I arranged the indexes according to the costs, to keep it simple).

So now, running the algorithm returns:

B(7, a5) = { a5 X B(2, a3)} U B(7, a3)

As the budget 2 is less than c3, B(2, a3) = B(2, a2)

As the budget 2 equals c2, B(2, a2) = {"a2"} U B(2, a1)

As the budget 2 >= c1, B(2, a1) = "a1" and thus B(2, a3) = {"a1", "a2"}

As 7 > c3, B(7, a3) = {a3 X B(4, a2)} U B(7, a2)

As 4 > c2, B(4, a2) = {a2 X B(2, a1)} U B(4, a1)

As a1 is the last and 2 >= c1, B(2, a1) = {"a1"}

As a1 is the last item and 4 >= c1, B(4, a1) = {"a1"} and thus B(4, a2) = {"a1a2", "a1"}

As 7 > c2, B(7, a2) = B(4, a2) = {"a1a2", "a1"}

B(7, a3) = {a3 X {"a1a2", "a1"}} U {"a1a2", "a1"}

B(7, a3) = {"a1a2a3", "a1a3"} U {"a1a2", "a1"}

B(7, a3) = {"a1", "a1a2", "a1a3", "a1a2a3"}

B(7, a5) = {a5 X B(2, a3)} U B(7, a3) = {a5 X {"a1", "a2"}} U B(7, a3) = {"a1a5", "a2a5"} U {"a1", "a1a2", a1a3", "a1a2a3"} = {"a1", "a1a2", "a1a3", "a1a5", "a2a5", "a1a2a3"}

We now remove the subsets: "a1", "a1a2", "a1a3" are all subsets of "a1a2a3"

These leaves us with "a1a5", "a2a5", "a1a2a3"

-

Let $B$ be the budget, let $c_1 \le c_2 \le \dots \le c_N$ be the valuesof the $N$ items, ordered increasingly. Let $C_n = \sum_{i =1}^n c_i$ be the cost of the $n$ cheapest items.

You'll never be able to take more than $M = \max \{n : C_n \le B\}$ items (take cheap items as long as you can afford) and you'll always be able to take at least $m = \max \{j : C_N - C_{N-j} \le B\}$ items (take expensive items as long as you can afford). This will give you an idea of the size of the search space: Its size is bounded by $\sum_{j=m}^M {{N}\choose{j}}$. In your case, $N \approx 40, M \le 12, \, m \ge 2$ and so the sum could be as large as $10^{10}$.

To organize a search through all choices, identify a selection with a vector $x \in \{0,1\}^N$ where 1 means "take this item". So taking the $M$ cheapest items means $x_0 = (1,1,\dots, 1, 0, \dots, 0)$, where there are $M$ 1's.

Start with this $x_0$ and generate all other such vectors with $k = M$ 1's in reverse dictionary order and record them as possible selection, as long as their total cost does not exceed you budget. Once your budget is exceeded, stop.

Repeat with vectors with $k = M-1, \dots, m$ entries, in this order. For each selection, check if the cheapest item not taken could still fit in the budget. If it does, do not include this selection, you have already recorded it. Stop if you reach $k$ items that you cannot afford and repeat with $k$ replaced by $k-1$. You are done when you have stopped on $k = m$, which will give you the selection $(0, \dots, 0, 1, \dots, 1)$ with $m$ 1's.

-
It took me some time to run this through a sample and understand it. This is a totally great and correct answer - thanks! – Avi Nov 25 '12 at 10:14
I took some time to think about it, and I'm not sure I understand whether this works. The idea at the k'th step is to traverse the vectors in reverse dictionary order, and stop when the budget is exceeded. According to en.wikiversity.org/wiki/Lexicographic_and_colexicographic_order, this is equivalent to traversing the combinations in lex order. Assume that for each n cn equals n, the the budget equals 10, N is 6 and k=3. When we reach <1,4,6> the sum is 11 and we should stop. However, had we continued to <2,3,4>, the sum would be 9 we would have been within budget again! – Avi Nov 27 '12 at 12:06
Would appreciate if you took a look. – Avi Dec 1 '12 at 14:14