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.

Is it necessary that at most one item from each category (Shirt, Pants, Shoes) is selected? — Codor
– Codor, Commented Jul 15, 2015 at 13:28
Search for an optimisation algorithm. You'll want to look at the various types that exist, and figure out whether or not this problem falls within the exact type they can solve. Note that at worst, if this is a form of bin-packing problem, the optimal solution is NP-hard. — Marcin
– Marcin, Commented Jul 15, 2015 at 13:29
Why is the 15-30-15 option better than 20-20-20? (If you can answer this question, you are probably a good deal closer to finding the algorithm) — tobias_k
– tobias_k, Commented Jul 15, 2015 at 13:29
Note also that if one from each category must be selected this problem is easier than if it is unconstrained. — Marcin
– Marcin, Commented Jul 15, 2015 at 13:30

Codor · Accepted Answer · 2015-07-15 20:32:50Z

3

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.

edited Jul 15, 2015 at 20:32

answered Jul 15, 2015 at 15:34

Codor

17.6k9 gold badges32 silver badges59 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

dlask · Accepted Answer · 2015-07-15 14:42:33Z

0

Just a fun with Python's itertools:

import itertools

def solutions(dicts, value):
    return [keys for keys in itertools.product(*dicts) if sum(d[k] for d, k in zip(dicts, keys)) == value]

Shirt = {"shirtA": 20, "shirtB": 15, "shirtC": 10}
Pants = {"pantsA": 30, "pantsB": 25, "pantsC": 20}
Shoes = {"shoesA": 20, "shoesB": 15, "shoesC": 10}

print solutions([Shirt, Pants, Shoes], 60)

We generate all allowed combinations (one piece from each category) but we keep only these that give the required sum.

answered Jul 15, 2015 at 14:42

dlask

9,0421 gold badge29 silver badges31 bronze badges

Collectives™ on Stack Overflow

what algorithm should I use?

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related