Maximize sum(x)
subject to constraint:
P•x = 43.94
where P is a vector of prices of each toy, and x is a vector of quantities purchased of each toy.
Then one can either plug this into an LP solver, or can solve it by hand using simplex or other algorithm.
If we add the constraint that x must be an integer vector, then it becomes an integer linear program. Solving integer linear programs is NP-complete.
from itertools import combinations
arr = [
("yoyo",1.22),("doll",2.75),("duckie",1.85),("tractor",5.97),("airplaine",6.47),
("ball",2.16),("racecar",7.13),("dog",4.57),("jumprope",1.46),("car",5.18),
("elephant",3.16),("bear",4.89),("xylophone",7.11),("tank",6.45),("checkers",4.77),
("boat",8.04),("train",6.71),("jacks",2.31),("truck",6.21),("whistle",0.98) ("pinwheel",0.87)
]
for r in range(1,len(arr)+1):
for thisset in list(combinations(arr, r)):
if 43.94==sum([tup[1] for tup in thisset]):
print ([tup[0] for tup in thisset])You could also construct a graph, where every price is a node. Start at 0.00, and do a BFS until you find the desired price. Worst case scenario O(n) where n is the desired price. Could be optimised by using a path finding algorithm like A*, its heuristic would make it try a greedy algorithm at first and then do a more complex solve at the end.
Another possibility is by memoization (dynamic programming). Strictly worse than the graph algorithm in complexity terms, but in practice your computer is very good at working sequentially on a very big array of booleans.
Really many different approaches to solve this problem. In this specific case greedy worked as well.