给定一个包含n个数字（1 <= n <= 100），每个数字都是1到450之间的整数，我们需要将这些数字分配到两个集合A和B中，以满足以下两种情况：
谢谢。
- 每个集合中的数字总数最多相差1。
- A集合中所有数字的总和应尽可能接近B集合中所有数字的总和，即分配应该是公平的。
谢谢。
13个回答
9
由于数字很小，它不是NP完全问题。
要解决它，您可以使用动态规划：
创建一个三维布尔表格，其中t[s, n, i]为true表示可以通过i下标以下的n个元素的子集达到和为s。要计算t[s, n, i]的值，请检查t[s, n, i-1]和t[s-a[i], n-1, i-1]。然后在第二个索引n/2中查找最佳解决方案。
编辑：实际上，您不需要一次性获取完整的表格。您可以为每个索引i创建一个二维表格t_i[s, n]，并从i-1的表格计算i的表格，因此您只需要两个这些二维表格，这可以节省大量内存。（感谢Martin Hock。）
- starblue
6
1有关DP的更详细描述，请参阅TopCoder DP教程（http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg）。 - Olexiy
3在这种情况下，无论输入的大小如何，该问题都是NP完全问题！ :-p 另一个问题是，考虑到其规模，该问题实例是否可行。 - fortran
输入值的约束条件（每个都<=450）使问题在多项式时间内可解决。可以愚蠢地用O(N^450)的暴力方法解决问题（这显然是多项式的）。另一个评论中描述了快速的N^3解决方案。 - Olexiy
3@fortran: 不行！NP完备性（或者类似“多项式时间”的概念）是基于输入规模定义的。这里描述的DP算法完全正确；它的运行时间是输入数字的多项式函数（此处为1到100）。之所以这不是通用数分割问题的多项式时间算法，仅仅是因为在那种情况下，“输入规模”是描述输入所需的位数，因此是输入数字的对数。 - ShreevatsaR
+1 哦，不错的解决方案。我知道有一种使用 DP 的下降伪多项式解决方案，但我想不到表格。感谢您的洞察力。 - Falaina
1你也可以使用2D表格来操作。当t[s, k]为真时表示，某个子集k的元素和可以达到s。你的数组大小应为[S，ceil(n/2)]，其中S是所有元素的总和，n是元素数量。然后遍历元素i [1] ... i [n]。 对于每个元素i [x]，扫描表格，如果t[s，n]为真，则将t[s + i[x]，n + 1]设置为真（除非会超出表格）。同时，将t[i[x]，1]设置为真。最后，扫描最后一列（[x，ceil（n/2）]中的所有x）以获取最佳值。 - Martin Hock
3
这是一个受限制的版本数字分割问题。通常的目标是找到任意两个不相交的子集，使它们的和之差最小。您的问题在于只考虑一种可能性：大小为N/2的两个集合（如果总数是奇数，则为一个大小为N/2的集合和一个大小为N/2+1的集合）。这大大减少了搜索空间，但我目前想不出一个好的算法，我会继续思考。
- Falaina
3
我的计算表明，将100个数字分成两组50个数字的方式有1.00891344545564e+29种（最坏情况），因此任何暴力解法仍然会失败！不过正如您的链接所说，数字分割被认为是NP完全问题中最容易的一种！ - Jackson
2只有当您将输入大小定义为输入的“长度”，即描述数字所需的位数时，数字分割问题（或背包问题或子集和问题）才是NP完全问题。但是，有易于实现的动态规划算法，其运行时间多项式地依赖于数字本身（这里是1到100）。因此，它是NP完全问题并不应该成为阻碍。（事实上，当数字的大小从n的多项式变为指数级别时，这些问题会经历“相变”...但100是一个非常小的数字，所以这里不需要担心。） - ShreevatsaR
简而言之：NP难问题的受限版本不一定是困难的。远非如此。 :-) - ShreevatsaR
2
没关系，我以为这些数字是顺序的。这看起来有点像NP难问题背包问题。
这些数字是按顺序排列的吗？
在最后一次迭代中，我们在步骤1处，剩余0、1 1、2 [1,2] 或 3 [1,2,3]个数字。
如果是0，则完成了，并且组的数量和重量相等。
如果是1，则将数字1分配给A组。 A组有一个额外的项目和一个额外的重量。在这种情况下，这是我们能做到的最公平的。
如果是2，则将数字2分配给A组，将数字1分配给B组。现在组具有相同数量的项目，并且A组有一个额外的重量。同样，在这种情况下，这是我们能做到的最公平的。
如果是3，则将数字3分配给A组，将数字2和1分配给B组。现在组具有相同的重量（3 == 2 + 1），并且B组有一个额外的项目。
这些数字是按顺序排列的吗？
- 将最大的数字放在A中。
- 将下一个最大的数字放在B中。
- 将下一个最大的数字放在B中。
- 将下一个最大的数字放在A中。
- 重复步骤1，直到所有数字都被分配完毕。
证明：
在每个4个数字的倍数被分配之后，A和B都包含相同数量的物品，并且每组中的物品总和相同，因为
(n) + (n - 3) == (n - 1) + (n - 2)
在最后一次迭代中，我们在步骤1处，剩余0、1 1、2 [1,2] 或 3 [1,2,3]个数字。
如果是0，则完成了，并且组的数量和重量相等。
如果是1，则将数字1分配给A组。 A组有一个额外的项目和一个额外的重量。在这种情况下，这是我们能做到的最公平的。
如果是2，则将数字2分配给A组，将数字1分配给B组。现在组具有相同数量的项目，并且A组有一个额外的重量。同样，在这种情况下，这是我们能做到的最公平的。
如果是3，则将数字3分配给A组，将数字2和1分配给B组。现在组具有相同的重量（3 == 2 + 1），并且B组有一个额外的项目。
- mob
2
虽然背包问题肯定是NP难的，但是（在输入约束下）这个问题可以在多项式时间内解决。 - Olexiy
1这种方法并不适用于所有情况，请尝试使用10、15、20、25、30、45、75。结果是A=75、25、20和B=45、30、15、10。A中的总和为120，B中的总和为100，而每个中都有可能达到110。 - Patrice Bernassola
2
如果数字是顺序的，那么你只需在A和B之间交替分配它们。
我怀疑它们不是顺序的，如果是这样...
将最大的未分配数字分配给总和较低的组，除非两个组之间的大小差异小于或等于未分配数字的数量（在这种情况下，将所有剩余数字分配给较小的组）。
这并不能在所有情况下找到最佳解决方案，但它接近且简单。
我怀疑它们不是顺序的，如果是这样...
将最大的未分配数字分配给总和较低的组，除非两个组之间的大小差异小于或等于未分配数字的数量（在这种情况下，将所有剩余数字分配给较小的组）。
这并不能在所有情况下找到最佳解决方案，但它接近且简单。
- RichH
2
1不幸的是，轮流分配并不能完全满足指定的目标。想象一下序列1、2、3：交替分配数字会给你A={1, 3}和B={2}，但更公平的分配应该是A={1, 2}和B={3}。 - C Pirate
我确实说过它找不到最佳解决方案，但这是一种非常简单的方法，可以找到接近的解决方案。 - RichH
2
首先，不考虑第一个限制条件（即尽可能使总和接近），找到问题的解决方案。可以使用DP方法解决这个问题（您可以在此处详细了解DP，而第一个与硬币有关的问题与您的问题非常相似）。
一旦您能够解决问题，就可以将另一个状态添加到您的DP中——已选择进入子集的人数。这将给出N^3的算法。
- Olexiy
3
这是正确的，但是一个小细节：算法是（N^2K），其中K是子集的最大大小（这里为100N），而不一定是通常的N^3。 - ShreevatsaR
450*N。 - Olexiy
是的，我知道。尽管450是一个“常数”，但将其视为参数并说算法是O（N^3*K）而不是O（N^3）更具信息量。 :-) - ShreevatsaR
2
我有一个算法要给你。它使用了许多递归和迭代的概念。
假设您有n个数字Xn，其中1 <= n <= 100且1 <= Xn <= 450。
1. 如果n < 3，则分配数字并停止算法。 2. 如果n > 2，则按升序对数字列表进行排序。 3. 计算所有数字的总和S。 4. 然后将先前的总和S除以(n - n%2)/2，得到A值。 5. 现在我们将创建一对数字，它们的加法尽可能接近A。获取第一个数字，然后找到第二个数字，以便获得与A最接近的和S1。将S1放入新的数字列表中，并记住如何计算总和，以便稍后使用基本数字。 6. 执行步骤5直到列表中的数字<2。然后将剩余的数字放入总和列表中，并使用新列表重新启动算法到步骤1。
示例：
假设：n = 7，数字为10、75、30、45、25、15、20
Pass 1:
由于n>2，因此对列表进行排序：10、15、20、25、30、45、75
总和S=220
A=220/((7-1)/2)=73
夫妻：
10 & 75 => 85
15 & 45 => 60
20 & 30 => 50
剩余数字<2，因此将25添加到总和列表中：85(10,75)，60(15,45)，50(20,30)，25(25)
Pass 2:
n=4，数字为85、60、50、25
列表计数>2，因此对列表进行排序：25(25)，50(20,30)，60(15,45)，85(10,75)
总和S仍然相同(S=220)，但必须重新计算A：A=220/((4-0)/2)=110
夫妻：
25 & 85 => 110
50 & 60 => 110
总和列表为：110(25(25),85(10,75))，110(50(20,30),60(15,45))
假设您有n个数字Xn，其中1 <= n <= 100且1 <= Xn <= 450。
1. 如果n < 3，则分配数字并停止算法。 2. 如果n > 2，则按升序对数字列表进行排序。 3. 计算所有数字的总和S。 4. 然后将先前的总和S除以(n - n%2)/2，得到A值。 5. 现在我们将创建一对数字，它们的加法尽可能接近A。获取第一个数字，然后找到第二个数字，以便获得与A最接近的和S1。将S1放入新的数字列表中，并记住如何计算总和，以便稍后使用基本数字。 6. 执行步骤5直到列表中的数字<2。然后将剩余的数字放入总和列表中，并使用新列表重新启动算法到步骤1。
示例：
假设：n = 7，数字为10、75、30、45、25、15、20
Pass 1:
由于n>2，因此对列表进行排序：10、15、20、25、30、45、75
总和S=220
A=220/((7-1)/2)=73
夫妻：
10 & 75 => 85
15 & 45 => 60
20 & 30 => 50
剩余数字<2，因此将25添加到总和列表中：85(10,75)，60(15,45)，50(20,30)，25(25)
Pass 2:
n=4，数字为85、60、50、25
列表计数>2，因此对列表进行排序：25(25)，50(20,30)，60(15,45)，85(10,75)
总和S仍然相同(S=220)，但必须重新计算A：A=220/((4-0)/2)=110
夫妻：
25 & 85 => 110
50 & 60 => 110
总和列表为：110(25(25),85(10,75))，110(50(20,30),60(15,45))
第三步:
n = 2，数字为110, 110
n < 3，所以需要分配数字:
A = 25, 10, 75
B = 20, 30, 15, 45
我已经测试过，这在每种情况下都可以正常工作。
- Patrice Bernassola
2
这是一个不错的尝试，但它不可能适用于所有输入--因为如果这是正确的，那么就有可能扩展它并获得一个NP完全数分割问题的多项式时间算法。这注定会失败，但我现在想不出反例。你有这方面的代码吗？试试更大的数字（例如，使用一组接近450的10个数字，其中恰好有一个好的分区）。 - ShreevatsaR
实际上，我给另一个解决方案的相同反例仍然适用：取(19, 20, 21, 29, 31)。总和为120，因此您的算法将尝试找到两个接近120/((5-1)/2)=60的对：(19,31)和(20,29)。然后它将继续使用列表21(21), 49(20,29), 50(19,31)。接下来，它尝试找到总和为120/((3-1)/2)=120的对：(21,50(19,31))。因此，它以71(21,19,31)和49(20,29)的分区结束，但最佳分区是60(29,31)和60(19,20,21)。如果“配对”是从最大的数字开始完成的话，您的算法实际上可以在这个例子中工作，但这不能推广 :) - ShreevatsaR
1
@ShreevatsaR指出下面的算法被称为贪心算法。它在处理某些输入时表现不佳（我尝试了10组随机生成的大小为100的输入集，在所有情况下，总和非常接近，这让我认为对输入进行排序就足以使该算法成功）。
另请参见{{link1：“最简单的困难问题”，《美国科学家》杂志，2002年3-4月号}}，由ShreevatsaR推荐。
#!/usr/bin/perl
use strict;
use warnings;
use List::Util qw( sum );
my @numbers = generate_list();
print "@numbers\n\n";
my (@A, @B);
my $N = @numbers;
while ( @numbers ) {
my $n = pop @numbers;
printf "Step: %d\n", $N - @numbers;
{
no warnings 'uninitialized';
if ( sum(@A) < sum(@B) ) {
push @A, $n;
}
else {
push @B, $n;
}
printf "A: %s\n\tsum: %d\n\tnum elements: %d\n",
"@A", sum(@A), scalar @A;
printf "B: %s\n\tsum: %d\n\tnum elements: %d\n\n",
"@B", sum(@B), scalar @B;
}
}
sub generate_list { grep { rand > 0.8 } 1 .. 450 }
请注意，
generate_list 返回一个按升序排列的列表。- Sinan Ünür
12
这个算法也不能保证第二个约束条件，例如，对于列表{1, 1, 3, 3, 4}，它会产生类似{1, 3, 4}-{1, 3}的结果，而不是正确的答案{1, 1, 4} - {3, 3}。 - Olexiy
@Olexiy：在你给我点踩之前，你应该尝试运行一下这段代码。你好像忽略了我正在从主列表中进行“pop”操作的事实。 - Sinan Ünür
我错过了你从列表末尾弹出的事实 - 现在尝试 {4, 3, 3, 1, 1} - Olexiy
使用{2, 2, 2, 3, 3}。最优解是将其分成两个集合{2, 2, 2}和{3, 3}，均等于6，但是您的代码（我已运行）生成了{3, 2}和{3, 2, 2}，它们分别为5和7。您的想法是数值分割问题的差异启发式方法，虽然它适用于许多情况，但已知它在某些情况下可能与最优解相差甚远。 - ShreevatsaR
更正：您的想法被称为贪心算法；“差分”是由Karmarkar和Karp提出的另一个想法（效果更好，但仍不是最优解）。更多阅读资料：Brian Hayes的文章“最简单的困难问题”，American Scientist，2002年3-4月。http://www.americanscientist.org/issues/pub/the-easiest-hard-problem/ - ShreevatsaR
显示剩余7条评论
1
你在第二点的要求需要澄清，因为：“A中所有数字的总和尽可能接近B中所有数字的总和”是清晰明了的，但是你的陈述“分配应该公平”让一切变得不清楚。'公平'到底意味着什么？这个过程需要一个随机元素吗？
- 9b5b
1
谢谢你的回复Jon。所谓公平，我指的是每组数字的总和应尽可能相等，并且每组中的数字总数最多只能相差1。 - Ralph
0
如果您需要完美的答案，那么您必须生成并循环遍历所有可能的答案集。如果您只需要一个相当不错的答案，则模拟退火等技术是可行的方法。这里有一些使用非常原始的冷却计划来查找答案的C代码。
#include <stdio.h>
#include <stdlib.h>
#define MAXPAR 50
#define MAXTRIES 10000000
int data1[] = {192,130,446,328,40,174,218,31,59,234,26,365,253,11,198,98,
279,6,276,72,219,15,192,289,289,191,244,62,443,431,363,10
} ;
int data2[] = { 1,2,3,4,5,6,7,8,9 } ;
// What does the set sum to
int sumSet ( int data[], int len )
{
int result = 0 ;
for ( int i=0; i < len; ++i )
result += data[i] ;
return result ;
}
// Print out a set
void printSet ( int data[], int len )
{
for ( int i=0; i < len; ++i )
printf ( "%d ", data[i] ) ;
printf ( " Sums to %d\n", sumSet ( data,len ) ) ;
}
// Partition the values using simulated annealing
void partition ( int data[], size_t len )
{
int set1[MAXPAR] = {0} ; // Parttition 1
int set2[MAXPAR] = {0} ; // Parttition 2
int set1Pos, set2Pos, dataPos, set1Len, set2Len ; // Data about the partitions
int minDiff ; // The best solution found so far
int sum1, sum2, diff ;
int tries = MAXTRIES ; // Don't loop for ever
set1Len = set2Len = -1 ;
dataPos = 0 ;
// Initialize the two partitions
while ( dataPos < len )
{
set1[++set1Len] = data[dataPos++] ;
if ( dataPos < len )
set2[++set2Len] = data[dataPos++] ;
}
// Very primitive simulated annealing solution
sum1 = sumSet ( set1, set1Len ) ;
sum2 = sumSet ( set2, set2Len ) ;
diff = sum1 - sum2 ; // The initial difference - we want to minimize this
minDiff = sum1 + sum2 ;
printf ( "Initial diff is %d\n", diff ) ;
// Loop until a solution is found or all are tries are exhausted
while ( diff != 0 && tries > 0 )
{
// Look for swaps that improves the difference
int newDiff, newSum1, newSum2 ;
set1Pos = rand() % set1Len ;
set2Pos = rand() % set2Len ;
newSum1 = sum1 - set1[set1Pos] + set2[set2Pos] ;
newSum2 = sum2 + set1[set1Pos] - set2[set2Pos] ;
newDiff = newSum1 - newSum2 ;
if ( abs ( newDiff ) < abs ( diff ) || // Is this a better solution?
tries/100 > rand() % MAXTRIES ) // Or shall we just swap anyway - chance of swap decreases as tries reduces
{
int tmp = set1[set1Pos] ;
set1[set1Pos] = set2[set2Pos] ;
set2[set2Pos] = tmp ;
diff = newDiff ;
sum1 = newSum1 ;
sum2 = newSum2 ;
// Print it out if its the best we have seen so far
if ( abs ( diff ) < abs ( minDiff ) )
{
minDiff = diff ;
printSet ( set1, set1Len ) ;
printSet ( set2, set2Len ) ;
printf ( "diff of %d\n\n", abs ( diff ) ) ;
}
}
--tries ;
}
printf ( "done\n" ) ;
}
int main ( int argc, char **argv )
{
// Change this to init rand from the clock say if you don't want the same
// results repoduced evert time!
srand ( 12345 ) ;
partition ( data1, 31 ) ;
partition ( data2, 9 ) ;
return 0;
}
- Jackson
1
哈哈哈，用PERL解决NP问题！我现在见识到了一切！;-) - user140327
0
我假设这些数字不是连续的，而且你不能重新平衡？
由于限制1，你每隔一个插入就需要交换桶。所以每当你不被迫选择一个桶时，选择一个逻辑桶（添加该数字会使总和更接近另一个桶）。如果这个桶不是你先前选择的桶，则你可以再选择一次而不被迫。
- psychotik
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接