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$, $ 1\leq i \leq n$ be the objects we are dealing with, and $p_i$, $ 1\leq 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.