Python Forum
Dividing list into subsets
Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Dividing list into subsets
#2
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.
Reply


Messages In This Thread
Dividing list into subsets - by Michael11 - Oct-01-2020, 12:26 PM
RE: Dividing list into subsets - by deanhystad - Oct-01-2020, 09:08 PM
RE: Dividing list into subsets - by Michael11 - Oct-02-2020, 06:43 AM
RE: Dividing list into subsets - by deanhystad - Oct-02-2020, 10:34 PM
RE: Dividing list into subsets - by DPaul - Oct-04-2020, 09:47 AM
RE: Dividing list into subsets - by Michael11 - Oct-04-2020, 10:23 AM
RE: Dividing list into subsets - by DPaul - Oct-04-2020, 05:13 PM
RE: Dividing list into subsets - by Katenn - Oct-04-2020, 06:13 PM
RE: Dividing list into subsets - by DPaul - Oct-05-2020, 06:34 AM
RE: Dividing list into subsets - by deanhystad - Dec-11-2020, 09:51 PM
RE: Dividing list into subsets - by deanhystad - Dec-12-2020, 06:18 AM

Forum Jump:

User Panel Messages

Announcements
Announcement #1 8/1/2020
Announcement #2 8/2/2020
Announcement #3 8/6/2020