Timeline for Derive subset with sum between two values
Current License: CC BY-SA 3.0
21 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 9, 2015 at 15:22 | history | edited | Preston S | CC BY-SA 3.0 |
added 908 characters in body
|
| Sep 30, 2014 at 21:40 | history | tweeted | twitter.com/#!/StackProgrammer/status/517066388587167744 | ||
| Sep 30, 2014 at 15:47 | comment | added | David Hammen | Solutions to the knapsack problem inevitably use what you call "guess and check". | |
| Sep 30, 2014 at 15:46 | comment | added | David Hammen | Re Is there an algorithm to get the desired subset without using guess and check? Let M be the number of questions whose ranking is between 0.65 and 0.75. The answer to your question is yes if M>N. Just randomly choose N of those M questions. Otherwise, the answer is no. | |
| Sep 30, 2014 at 15:46 | comment | added | Preston S | @DavidHammen I understand it's not possible to find them all but is there a way to find just one? Maybe by using some variation of the knapsack problem? | |
| Sep 30, 2014 at 15:37 | comment | added | David Hammen | With the given example, 200 questions of which 50 are to be chosen, finding all the subsets of 50 that meet the requirement and choosing one at random is an unachievable task. There are 200 choose 50, or about 454 quattuordecillion (454*10^45), possible subsets. Some will be acceptable, others not. Your computer doesn't have the capacity to find all the acceptable subsets. Even Google or the NSA doesn't have that much storage (it's not even close). | |
| Sep 30, 2014 at 15:31 | history | edited | Preston S | CC BY-SA 3.0 |
added 20 characters in body
|
| S Sep 30, 2014 at 15:18 | history | suggested | AakashM | CC BY-SA 3.0 |
clarify with comments and edits incorporated
|
| Sep 30, 2014 at 14:35 | answer | added | Victor Victis | timeline score: 2 | |
| Sep 30, 2014 at 14:24 | comment | added | AakashM | I've attempted an edit to restate the problem with all the comments incorporated/addressed, hopefully it hasn't changed the problem. | |
| Sep 30, 2014 at 14:23 | review | Suggested edits | |||
| S Sep 30, 2014 at 15:18 | |||||
| Sep 30, 2014 at 13:03 | comment | added | Preston S | I've updated the question with more specific details and an example problem. | |
| Sep 30, 2014 at 13:00 | history | edited | Preston S | CC BY-SA 3.0 |
added 835 characters in body
|
| Sep 30, 2014 at 7:01 | comment | added | jwenting | as you set requirements as to the result your polling is giving, you're no longer talking about anything random... | |
| Sep 30, 2014 at 6:32 | comment | added | Doc Brown | A subset of which set? An arbitrary set of integers of size >= N? Only positive integers? A subset of the set of all positive integers? Please clarify! | |
| Sep 30, 2014 at 3:59 | comment | added | user40980 | Could you work through your problem? What are the constraints on the (sub)set? Are duplicates allowed? Are the values all integers? are they within a range? How do you handle that M may be a very big number? How random do you want the selection to be? | |
| Sep 30, 2014 at 3:57 | comment | added | Preston S | @DavidScholefield given that there are M subsets of size N that fulfill my condition, I want to select one of them at random. | |
| Sep 30, 2014 at 1:30 | comment | added | David Scholefield | I'm wondering how you are defining the 'randomness' of the subset? | |
| Sep 29, 2014 at 23:43 | comment | added | Ben Aaronson | en.wikipedia.org/wiki/Subset_sum_problem sounds similar | |
| Sep 29, 2014 at 22:58 | review | First posts | |||
| Sep 30, 2014 at 7:01 | |||||
| Sep 29, 2014 at 22:55 | history | asked | Preston S | CC BY-SA 3.0 |