3 ms·

Isn't this a knapsack problem [1]? It looks like it can be represented as a linear program: Maximize sum(x) subject to constraint: P•x = 43.94 where P is a

Isn't this a knapsack problem [1]? It looks like it can be represented as a linear program: 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. [1] https://en.m.wikipedia.org/wiki/Knapsack_problem https://en.m.wikipedia.org/wiki/Knapsack_problem

IncRnd 5y ago
Yep, except this is so small, you can look at all combinations. Something like this would do it (without replacement). 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])
- mkl 5y ago
  You're missing a comma before the pinwheel one, but otherwise this finds the same 686 solutions as mine.
  - deleted 5y ago
    [deleted]
  - IncRnd 5y ago
    You're correct... I must have made a mistake when pasting it into the HN edit box, since I performed slight edits to make it not jam into a single line. Thanks!
lqr 5y ago
The LP solver might find a solution with fractional toys. 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.
- sidpatil 5y ago
  Good point regarding ILP—that had slipped my mind.
mvanaltvorst 5y ago
Yes, this would work. Hard to reason about LP solvers in complexity notation, but would probably be pretty quick. 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.
asddubs 5y ago
it's subset sum, isn't it? https://en.wikipedia.org/wiki/Subset_sum_problem https://en.wikipedia.org/wiki/Subset_sum_problem

IncRnd 5y ago

Yep, except this is so small, you can look at all combinations. Something like this would do it (without replacement). 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])

mkl 5y ago
You're missing a comma before the pinwheel one, but otherwise this finds the same 686 solutions as mine.
- deleted 5y ago
  [deleted]
- IncRnd 5y ago
  You're correct... I must have made a mistake when pasting it into the HN edit box, since I performed slight edits to make it not jam into a single line. Thanks!

lqr 5y ago

The LP solver might find a solution with fractional toys. 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.

sidpatil 5y ago
Good point regarding ILP—that had slipped my mind.

mvanaltvorst 5y ago

Yes, this would work. Hard to reason about LP solvers in complexity notation, but would probably be pretty quick. 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.

asddubs 5y ago

it's subset sum, isn't it? https://en.wikipedia.org/wiki/Subset_sum_problem https://en.wikipedia.org/wiki/Subset_sum_problem