# “Knapsack problem” with repetition, “lesser or equal” constraint, and recording all valid combinations

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.