求算法：满足条件的排列组合
假设有一个随机数列{1,2，3，4，5....}
求其中相加为100的所数有组合，比方{{1,99},{1,2,97},{4,96}......}
自己想了一天，找不到解决办法。求师兄们指点
[解决办法]
类似于背包问题,递归来实现吧.
每个数字都可以选择2中状态,在组合里和不在组合里.
[解决办法]
#define ARRAY_SIZE(10)
int pArray[ARRAY_SIZE] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int pPrint[ARRAY_SIZE];
int nPrintPos;
int nTempSum;
int nSum;
void CheckSum(int nPos)
{
int i;
if(nSum == nTempSum)
{
printf( "%d = ", nSum);
for(i=0; i <nPrintPos-1; i++)
{
printf( "%d + ", pPrint[i]);
}
printf( " %d\n ", pPrint[i]);
return;
}
if(nPos < ARRAY_SIZE)
{
if(nTempSum+pArray[nPos] <= nSum)
{
nTempSum += pArray[nPos];
pPrint[nPrintPos++] = pArray[nPos];
CheckSum(nPos+1);
nPrintPos--;
nTempSum -= pArray[nPos];
}
CheckSum(nPos+1);
}
}
int main()
{
nTempSum = 0;
memset(pPrint, 0, sizeof(int)*ARRAY_SIZE);
nPrintPos = 0;
scanf( "%d ", &nSum);
CheckSum(0);
return 0;
}
垃圾代码,仅供参考.
[解决办法]
这样的问题用回溯法解决比较合适。
回溯法的效率瓶颈在于剪枝函数与限界函数的效率。
为了使回溯法的效率高，应该注意：
1：要有一个好的搜索次序。因此，将随机数列{1,2，3，4，5....}排序是有用的，因为这样剪枝函数就不盲目，更有效率。
2：在判断一个组合最后一个元素是否存在时，可用哈希表提高效率。比如：对一个三元组合，若已经确定前两个为1，2，现在要确定第三个元97是否在数列中，可用哈希查找。
另外，楼主所谓的“随机数列”，让人很不解。如果“随机数列”中有两个是一样的数，并且这个数包含在某个组合A中，那么A是算一个，还是两个？
[解决办法]
那复杂度是2^n了，有没有更好的算法那？
[解决办法]
回溯法：
#include <iostream>
using namespace std;
int list[20]={1,8,71,98,2,45,3,9,11,85,73,
5,61,54,38,79,28,18,21,31};
int Stack[10];
int Stacklen=0;
int s=0;
int GetMaxLen( )
{
int i=0, s=0;
while(s+list[i] <100)
s+=list[i++];
return i;
}
void Sort( )
{
int i, j, temp;
for( i=0; i <20; ++i )
{
for( j=i+1; j <20; ++j )
{
if( list[i]> list[j] )
{
temp=list[i];
list[i]=list[j];
list[j]=temp;
}
}
}
}
void Found( int f, int len, int sum )
{
int i;
if( len==0 )
{
if( s==100 )
{
cout < < "{ ";
for( i=0; i <Stacklen-1; ++i )
cout < <Stack[i] < < ", ";
cout < <Stack[i] < < "} " < <endl;
}
return ;
}
i=f;
while( list[i]+s <=100 && i <20 )
{
Stack[Stacklen]=list[i];
s+=list[i];
++Stacklen;
if( Stacklen==1 )
Found(f+1, len-1, sum-list[i]);
else
if(Stack[Stacklen-2] <Stack[Stacklen-1])
Found(f+1, len-1, sum-list[i]);
--Stacklen;
s-=list[i];
++i;
}
}
int main()
{
Sort();
int i, Maxlen=GetMaxLen();
for( i=2; i <=Maxlen; ++i )
Found( 0, i, 100 );
system( "PAUSE ");
return 1;
}
------解决方案--------------------
如果要找比回溯法更好的算法，那就可能要消耗空间来换取时间了。
记f(start,len,sum)为以在排完序的数列中序号为start首元，长度为len，和为sum的所有组合的集合。
注意到：回溯法重复解了许多子问题，为了避免这个问题，可以将子问题的解保存在一个表中，这个思路就是动态规划了。
比如：一个组合长度为6，已经确定头3个数，头3个中最大者在排完序的数列中序号是j,头3个数的和为20.如果在以前的搜索中,f(j+k,3,80)(0 <k <100-j)已经知道，那么将头三个数和f(j+k,3,80)连接起来输出就可以了。
但是，由于楼主要找的是所有组合，保存的解是相当多的，空间消耗太大。
有一个减少空间的办法：用一位表示一个元在一个组合中的状态：0表示不在这个组合中；1表示在这个组合中。设数列长度为L，那么任何一个组合都只需要L/8个字节。
[解决办法]
==========================================
那复杂度是2^n了，有没有更好的算法那？
==========================================
其实我上面说的回溯法，就已经能在8秒钟之内给出全部解了。虽然复杂度是O(2^n)，但是，通过剪枝，其实数据量并不大，我用从1到100的长度为100的自然数数列进行测试，用文件输出，结果只用了7秒钟，就得出全部的组合，总个数为444793个。
附上我的测试用的程序：
#include <iostream>
#include <fstream>
#include <windows.h>
using namespace std;
ofstream file( "data.txt ");
const int Max=100;
const int Sum=100;
int list[Max];
int Stack[Max];
int Stacklen=0;
int s=0;
int c=0;
int GetMinLen( )
{
int i=Max-1, s=0, len=0;
while( s+list[i] <Sum && i> =0 )
s+=list[i--],++len;
return len;
}
int GetMaxLen( )
{
int i=0, s=0;
while(s+list[i] <Sum && i <Max)
s+=list[i++];
return i;
}
void Found( int f, int len, int sum )
{
int i;
if( len==0 )
{
if( s==Sum )
{
file < < "{ ";
for( i=0; i <Stacklen-1; ++i )
file < <Stack[i] < < ", ";
file < <Stack[i] < < "} " < <endl;
++c;
}
return ;
}
i=f;
while( list[i]+s <=Sum && i <Max )
{
Stack[Stacklen]=list[i];
s+=list[i];
++Stacklen;
if( Stacklen==1 )
Found(f+1, len-1, sum-list[i]);
else
if(Stack[Stacklen-2] <Stack[Stacklen-1])
Found(f+1, len-1, sum-list[i]);
--Stacklen;
s-=list[i];
++i;
}
}
int main()
{
int i;
for( i=0; i <Max; ++i )
list[i]=i+1;
int time=GetTickCount();
int Maxlen=GetMaxLen();
int Minlen=GetMinLen();
for( i=Minlen; i <=Maxlen; ++i )
Found( 0, i, Sum );
cout < < "Total : " < <c < <endl;
cout < < "Use time : " < <GetTickCount()-time < < " ms\n ";
cout < < "请打开文件 'data.txt '查看结果!\n ";
system( "PAUSE ");
return 1;
}
