将数字分配给两个“容器".并最小化它们的总和之差 [英] Distribute numbers to two "containers" and minimize their difference of sum

问题描述

假设有n个数字，假设我们有以下4个数字15,20,10,25

Suppose there are n numbers let says we have the following 4 numbers 15,20,10,25

有两个容器A和B，我的工作是向它们分配数字，以使每个容器中数字的总和具有最小的差异.

在上面的示例中，A应该具有15 + 20，而B应该具有10 + 25.所以差异= 0.

In the above example, A should have 15+20 and B should have 10+ 25. So difference = 0.

我想到一种方法.看来可行，但我不知道为什么.

I think of a method. It seems to work but I don't know why.

首先按降序对数字列表进行排序.在每个回合中，取出最大数目 放在容器中的总金额更少.

Sort the number list in descending order first. In each round, take the maximum number out and put to the container have less sum.

顺便说一句，DP可以解决吗? THX

Btw, is it can be solved by DP? THX

推荐答案

1. 实际上，您的方法并不总是有效.考虑一下2,4,4,5,5.您的方法得到的结果将是(5,4,2)(5,4)，而最佳答案是(5,5)(4,4,2).

1. In fact, your method doesn't always work. Think about that 2,4,4,5,5.The result by your method will be (5,4,2)(5,4), while the best answer is (5,5)(4,4,2).

是的，可以通过动态编程解决.以下是一些有用的链接:

Yes, it can be solved by Dynamical Programming.Here are some useful link:

教程和代码: http://www.cs.cornell .edu/〜wdtseng/icpc/notes/dp3.pdf
练习: http://people.csail.mit.edu/bdean/6.046/dp/(然后单击Balanced Partition)

Tutorial and Code: http://www.cs.cornell.edu/~wdtseng/icpc/notes/dp3.pdf
A practice: http://people.csail.mit.edu/bdean/6.046/dp/ (then click Balanced Partition)

此外，请注意，如果问题的规模非常大(例如您有500万个数字等)，则您将不希望使用需要太大矩阵的DP.在这种情况下，您想使用一种 Monte Carlo 算法:

1. 将n个数字随机分为两组(或根据需要在此步骤中使用您的方法)；
   
2. 从每个组中选择一个数字，
   如果(交换这两个数字以减少总和的差)交换它们；
   
3. 重复步骤2，直到长时间没有发生交换".

1. divide n numbers into two groups randomly (or use your method at this step if you like);
   
2. choose one number from each group,
   if (to swap these two number decrease the difference of sum) swap them;
   
3. repeat step 2 until "no swap occurred for a long time".

您不希望这种方法总能找到最佳答案，但这是我知道在合理的时间和内存范围内以非常大规模解决此问题的唯一方法.

You don't want to expect this method could always work out with the best answer, but it is the only way I know to solve this problem at very large scale within reasonable time and memory.

这篇关于将数字分配给两个“容器".并最小化它们的总和之差的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！