patternMinor
Variation of knapsack problem
Viewed 0 times
knapsackproblemvariation
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?
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?
Solution
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).
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).
Context
StackExchange Computer Science Q#82376, answer score: 2
Revisions (0)
No revisions yet.