我是否需要为以下内容形成所有排列和组合？

Question

您有许多已知重量 w1, …, wn 的石头。

编写一个程序，将石头重新排列成两堆，使两堆之间的重量差异最小。

Answer 1

没有。您无需创建所有 2^n 组合。有两种方法可以避免它。

即使您会创建很多组合并进行比较，您也可以使用初步过滤。虽然您只完成了组合的一部分，设置了 m (m < n) 颗棋子，但有时您可以检查是否可以从中发展出一个好的组合。例如，其中一堆中的重量可能已经太大了。
也许您可以找到一些现有算法，无需任何组合即可创建所需的合成。您可以自己发明它或找到一个已经存在的。

即使您找到了算法，请记住，您也必须学习如何创建自己的算法来进行初步筛选排序。因为在现实生活中有很多任务需要这个技能。

Answer 2

虽然这是一个一维背包问题，但这里有另一种数学方法。

Algorithm: 1D Optimization
Input: weights (sequenc of weights)
Output: left and right, two sequences with difference between sum of elements minimized
***************************************************************************************

1) Sort weights in descending order
2) initialize leftsum = 0, rightsum = 0
3) initialize leftseq = [], rightseq = []
4) for each weight in weights repeat
 4.1) if leftsum = 0 then
  4.1.1) leftsum = weight
  4.1.2) leftseq.add(weight)
 4.2) else if rightsum = 0 then
  4.2.1) rightsum = weight
  4.2.2) rightseq.add(weight)
 4.3) else
  4.3.1) error_left = absolute(leftsum - weight)
         error_right = absolute(rightsum - weight)
  4.3.2) if error_left >= error_right then
   4.3.2.1) rightsum = rightsum + weight
   4.3.2.2) rightseq.add(weight)
  4.3.3) else
   4.3.3.1) leftsum = leftsum + weight
   4.3.3.2) leftseq.add(weight)
 

// And here is a sample implementation of the above hypothesis in python

numbers = [1, 23, 100, 857, 890, 78, 54, 789, 34, 47, 900];
#numbers = [1, 23, 16, 5, 2]
print numbers
numbers.sort(reverse=True)
print numbers

leftSum = 0;
rightSum = 0;

leftSeq = [];
rightSeq = [];

for num in numbers:
 if leftSum == 0:
  leftSum = num;
  leftSeq.append(num);
 elif rightSum == 0:
  rightSum = num;
  rightSeq.append(num);
 else:
  errorLeft = abs(leftSum - num);
  errorRight = abs(rightSum - num);
  if errorLeft >= errorRight:
   rightSum += num;
   rightSeq.append(num);
  else:
   leftSum += num;
   leftSeq.append(num);

print leftSum;
print rightSum;
print leftSeq;
print rightSeq;

应该可以。您的序列现在位于 leftseq 和 rightseq 中。

我是否需要为以下内容形成所有排列和组合？

Would I need to form all permutations and combinations for the following?

c

algorithm

dynamic-programming

brute-force