我找不到解决此类问题的好方法: 我们有 5 <= k <= 50 个片段，长度从 1 到 1000 个单位。 程序必须从这些部分构建两个长度相同的支柱。 程序必须找出柱子的最大可能长度。
例如: 5 段长度:1 5 2 3 4 正确的解是:第一柱2+5=7，第二柱3+4=7。
你会如何处理？
最佳答案
维基百科有一篇关于 the Partition Problem in Computer Science 的文章其领导听起来像你想做的。
In computer science, the partition problem (or number partitioning1) is the task of deciding whether a given multiset S of positive integers can be partitioned into two subsets S1 and S2 such that the sum of the numbers in S1 equals the sum of the numbers in S2. Although the partition problem is NP-complete, there is a pseudo-polynomial time dynamic programming solution, and there are heuristics that solve the problem in many instances, either optimally or approximately. For this reason, it has been called "the easiest NP-hard problem".
引用了几种不同的算法来提供解决方案。
另请参阅以下内容。
Is partitioning an array into halves with equal sums P or NP?
关于2行相同长度的C++算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/38437503/