what algorithm should I use?

Question

I'm fairly new to complex algorithms (been doing simple programs til now), and I'm trying to develop a program where the user can input a desired budget, and the program would search for the optimal products the user can purchase from each category. example:

Products:
Shirt:
shirtA - $20
shirtB - $15
shirtC - $10
Pants:
pantsA - $30
pantsB - $25
pantsC - $20
Shoes:
shoesA - $20
shoesB - $15
shoesC - $10

User Input (budget): $60

Output:
shirtB - $15
PantsA - $30
shoesB - $15
total: $60

...or something like that. what kind of algorithm should I be researching for? I find this hard because I do not know where to begin in understanding what algorithm to use. See, this is for class, and our professor wants us to indicate what kind of algorithm we used. I think I can actually finish this if I just brute force trial and error this thing, but then I wouldn't know what algorithm I used. anyway, thanks guys.

Answer 1

The problem is a variation of the Knapsack problem; instead of choosing whether an item is to be included in the solution, a choice must be made which item to take from each category. Although not explicitly stated in the Wikipedia article, the formulation in the question can be solved within a pseudopolynomial runtime bound via Dynamic programming by modifying the recurrence relation for the basic formulation.