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 


*

*write software that would find all affordable solutions, then 

*group the affordable selections according to the attributes and identify preferred ones

*find which selections are robust against other players moves (i.e. can't be easily "blocked")

*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.

 A: 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
A: 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.  
A: 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"
