Oct-01-2020, 09:08 PM
(This post was last modified: Oct-01-2020, 09:08 PM by deanhystad.)
So the answer is | 2 4 4 | 5 5 | 8 | ?
2+4+4 = 10, 5+5 = 10, 8 = 8
There are some assumptions to be made. The first is that you will always have 3 subsets. Placing two sticks next to each other results in a sum of 0, and that is obviously not going to be the largest subset sum. It is also obvious that there will always be a stick before the first element and after the last element. Three subsets means you only have two sticks to move.
To solve the example list we would start like this:
| 2 | 4 4 5 5 | 8 |
You could do an exhaustive search:
| 2 | 4 4 5 5 | 8 | = 2
| 2 | 4 4 5 | 5 8 | = 2
| 2 | 4 4 | 5 5 8 | = 2
| 2 | 4 | 4 5 5 8 | = 2
| 2 4 | 4 5 5 | 8 | = 6
| 2 4 | 4 5 | 5 8 | = 6
| 2 4 | 4 | 5 5 8 | = 6
| 2 4 4 | 5 5 | 8 | = 8
| 2 4 4 | 5 | 5 8 | = 5
| 2 4 4 5 | 5 | 8 | = 5
This will guarantee you find the best solution, or at least a solution that ties for best. Since there are only 3 subsets even fairly large lists could be processed quite quickly. Play around with the order of the search and multiple algorithms practically leap out at you.
2+4+4 = 10, 5+5 = 10, 8 = 8
There are some assumptions to be made. The first is that you will always have 3 subsets. Placing two sticks next to each other results in a sum of 0, and that is obviously not going to be the largest subset sum. It is also obvious that there will always be a stick before the first element and after the last element. Three subsets means you only have two sticks to move.
To solve the example list we would start like this:
| 2 | 4 4 5 5 | 8 |
You could do an exhaustive search:
| 2 | 4 4 5 5 | 8 | = 2
| 2 | 4 4 5 | 5 8 | = 2
| 2 | 4 4 | 5 5 8 | = 2
| 2 | 4 | 4 5 5 8 | = 2
| 2 4 | 4 5 5 | 8 | = 6
| 2 4 | 4 5 | 5 8 | = 6
| 2 4 | 4 | 5 5 8 | = 6
| 2 4 4 | 5 5 | 8 | = 8
| 2 4 4 | 5 | 5 8 | = 5
| 2 4 4 5 | 5 | 8 | = 5
This will guarantee you find the best solution, or at least a solution that ties for best. Since there are only 3 subsets even fairly large lists could be processed quite quickly. Play around with the order of the search and multiple algorithms practically leap out at you.