Timeline for Going deeper with pseudo-polynomial time algorithm for set partitioning
Current License: CC BY-SA 3.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 27, 2015 at 14:02 | comment | added | Yuval Filmus | You can probably make do with $M$ due to symmetry (if $\sum_{i=1}^m x_i w_i = 0$ then $\sum_{i=1}^m (-x_i) w_i = 0$), but it's probably a better idea to allow negative sums (so the table is $n\times 2M$). | |
| Mar 27, 2015 at 13:53 | comment | added | kowal66b |
So the table will have size of Mxn where M is the sum of all the integers, and n is the number of ints? Or maybe 2M because the number can be also negative?
|
|
| Mar 27, 2015 at 13:49 | comment | added | Yuval Filmus | You should keep track of all possible values of $\sum_{i=1}^m x_i w_i$ at any given point. Whenever you find that $0$ is possible, you go back and construct the corresponding $x$s. That's the basic idea. | |
| Mar 27, 2015 at 13:47 | comment | added | kowal66b | Ok, but I'm just wondering about the proccess of filling the table. Should I fill it with minimal value of previous states (set with less numbers) + {-1,0,1}*(next w_i) and after that backtracking the result that have sum of all = 0? | |
| Mar 27, 2015 at 13:34 | comment | added | Yuval Filmus | No, writing pseudocode is your job. | |
| Mar 27, 2015 at 12:32 | comment | added | kowal66b | could you please help with this second approach and write down the simple pseudo code with I can fallow. Thank you. | |
| Mar 27, 2015 at 11:48 | vote | accept | kowal66b | ||
| Mar 27, 2015 at 11:06 | comment | added | kowal66b | It should be more simple if I know that all of the numers are positive integers and the sum S is less then 10^6. | |
| Mar 27, 2015 at 0:27 | history | answered | Yuval Filmus | CC BY-SA 3.0 |