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.