2 ms·
There's actually 21 items in the set, so 2097151 non-empty zero-or-one combinations. By the way, Leo says that some kids actually solved the problem exactly, s
by userbinator 5y ago
There's actually 21 items in the set, so 2097151 non-empty zero-or-one combinations.
By the way, Leo says that some kids actually solved the problem exactly, so there may be a trick that wasn’t obvious to Leo or me, or maybe they just got lucky.
Possibly they did something similar to https://en.wikipedia.org/wiki/Subset_sum_problem#Pseudo-polynomial_time_dynamic_programming_solution https://en.wikipedia.org/wiki/Subset_sum_problem#Pseudo-poly... ?
- deckar01 5y agoThe AZSPCS Sums of Powers problem was similar [0]. I found the optimizations surprisingly convoluted for how little of a speed up they provide. Writing an efficient backtracking, depth-first search was fun though. [0]: http://azspcs.com/Contest/SumsOfPowers http://azspcs.com/Contest/SumsOfPowers
- jameshart 5y agoIT doesn't say you can only buy zero or one of each item - in fact, the setup is explicitly that the toys are to be donated, meaning that we aren't likely to care too much about buying duplicates.