"Knapsack problem" with repetition, "lesser or equal" constraint, and recording all valid combinations

Question

In a game I am developing I came across an interesting problem, that seems like it could be solved using some modified variant of the knapsack problem, but it's a bit over my head.
Let $x_i$, $ 1leq i leq n$ be the objects we are dealing with, and $p_i$, $ 1leq i leq n$ the cost associated with each item.
Suppose there exists some total budget $B$.
I now need to find all combinations of items, such that:

the sum of their costs is lesser than or equal to the budget $B$
each object $x_j$ may appear any number of times, including not at all

This doesn't seem like a traditional optimization problem anymore, since I actually need to find all combinations that fulfill these constraints. How can this be solved efficiently? I was thinking about trying to modify the dynamic programming approach employed to solve the traditional knapsack problem, but it's a bit over my head.

vonbrand · Answer

The number of solutions can easily be huge, so just writing out the solutions will take a long time. But this is not the knapsack problem, which gives you a budget (knapsack capacity) and values of the items, and ask for maximal value (or if some value is atainable).
One way to generate them all is to use backtracking: List all solutions that don't include object 1, then all that do include object 1 once, twice, ... Recursively check for solutions without/with object 2, ... I don't think there can be any more efficient way, and it does prune off combinations that are doomed (can't be extended).
Look if you can narrow the search somehow. Say order the objects so that you get promising combinations early, and cut off the search when you get enough of those.

"Knapsack problem" with repetition, "lesser or equal" constraint, and recording all valid combinations

One Answer

Add your own answers!

Ask a Question