Variation of knapsack problem

I have a menu of n items, with each item having a value. Given the total amount spent, I have to figure out all the possible combinations of items purchased. Example, I have three menu items:

item 1: $4 item 2:$5

item 3: $8 with the total purchase price =$14

There is only one solution in the case, 1 purchase of item 1 and 2 purchases of item 2.

How do I go about solving this?

• Welcome to Computer Science! The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! Oct 12, 2017 at 17:50
• Welcome to Computer Science! What have you tried? Where did you get stuck? We do not want to just hand you the solution; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for tips on asking questions about exercise problems. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? Oct 12, 2017 at 17:50
• should you print all solutions or only print the number of them? Jul 10, 2018 at 15:24

This is called the subset sum problem. There's lots written about the problem; go read about it.

How you could have figured this out on your own: you already know it is a variant of the knapsack problem, so if you had read the Wikipedia page on the knapsack problem, you would have encountered a description of the subset sum problem in the section of that page on variations of the knapsack problem. In the future, I encourage you to do research before posting, to make sure your question isn't already answered in the obvious places (e.g., Wikipedia, textbooks).

• I believe this is a different problem. The subset sum problem does not deal with more than one of each item purchased as mine does. Oct 12, 2017 at 18:00
• @mcgillian, OK. I'd suggest you study the techniques for the subset problem and see how they apply here. Many of those same techniques for the knapsack problem and the subset sum problem can be adapted to your version.
– D.W.
Oct 12, 2017 at 18:18
• @mcgillian, then it is multisubset problem. Mar 12, 2018 at 11:17

Basically to solve these type of problems we make use of Inclusion-exclusion principle. For each element which in this case are purchasable items with some monetary value, we have a choice either to buy the item or to not buy it. If we buy the item then it is an instance of inclusion of item and we choose not to buy it then it is an instance of exclusion.

So we can say that for each item we have two possible choices and because of these two choices for each item these problems can be solved in exponential time recursively. Surely, Dynamic programming comes handy to optimize it to polynomial time.

Also i noticed that the problem is similar to coin change problem. You can go through this problem as well and see the inclusion-exclusion principle in action.