Skip to main content
Computer Science

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

Required fields*

5
  • 1
    $\begingroup$ Notice, that instead of finding the smallest maximal part, you can look for a number $W$ such that you can split array into parts with weights not larger then $W$. For given $W$ you can use it greedy algorithm. Now to find minimal $W$ notice that if there is partition with weights not larger then $W$ then also exists a partition with weights not larger then $W+1$ $\endgroup$ Commented May 16, 2020 at 22:49
  • $\begingroup$ Start with a balanced partition: let target weight be sum of weights divided by number of partitions. Accumulating, when exceeding the current target, check whether sum before or after current element was closer. Adjust target value. $\endgroup$ Commented May 17, 2020 at 5:10
  • $\begingroup$ @SzymonStankiewicz, I've made a Greedy algorithm that will simply create partitions not exceeding a target which is set to the average partition weight, and whatever is left is assigned to the last partition. This has the downside that the last partition can become quite a bit larger than the optimal. How do you suggest to improve this? Should I iterate the algorithm increasing the target or...? I'm not sure I quite understand your comments correctly, so maybe you can elaborate? (I've updated my question with the greedy algorithm) $\endgroup$ Commented May 17, 2020 at 17:39
  • $\begingroup$ @FilipA Are all weight positive? $\endgroup$ Commented May 17, 2020 at 18:56
  • $\begingroup$ It looks like my answer just expounds @Szymon's comment. $\endgroup$ Commented May 18, 2020 at 0:58