Timeline for Find all maximal subsets of a set of integers whose sum does not exceed a number
Current License: CC BY-SA 2.5
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 17, 2013 at 19:07 | comment | added | user2759990 | Here is a solution implemented in Python: docs.google.com/document/d/… Regards, Auden RovelleQuartz | |
| Mar 7, 2011 at 0:16 | comment | added | Charles | You should be able to 'efficiently' answer this problem with dynamic programming, since at every point either you have a solution or one or more elements of the set can be added to the collection. I quote "efficiently" because the number of subsets is likely to be large and so even if the algorithm is linear in the size of the output it could be quite time-consuming. A small modification to the algorithm would allow multisets rather than sets. | |
| Mar 5, 2011 at 20:39 | answer | added | user9072 | timeline score: 2 | |
| Mar 4, 2011 at 16:44 | comment | added | user9072 | While this is essentially contained in the previous comment, the additional key-word 'subset sum problem' might also be of help, see en.wikipedia.org/wiki/Subset_sum_problem | |
| Mar 4, 2011 at 16:40 | history | edited | Arturo Magidin |
edited tags
|
|
| Mar 4, 2011 at 16:18 | comment | added | Emil Jeřábek | The 0-1 knapsack problem (en.wikipedia.org/wiki/Knapsack_problem) asks to find the maximum achievable sum in the situation you describe. | |
| Mar 4, 2011 at 16:18 | comment | added | Chris Aholt | Sounds like the knapsack problem. | |
| Mar 4, 2011 at 16:12 | history | asked | asteriosk | CC BY-SA 2.5 |