void MergeLines( int * temp, int * A, int left, int right)
//

![](http://images.csdn.net/syntaxhighlighting/OutliningIndicators/ExpandedBloc
kStart.gif) ![](http://images.csdn.net/syntaxhighlighting/OutliningIndicators/
ContractedBlock.gif) … {

// 先判断些特殊的边界条件

if (right - left < 1 )

return ;

if (right - left == 1 )
![](http://images.csdn.net/syntaxhighlighting/OutliningIndicators/ExpandedSubB
lockStart.gif) ![](http://images.csdn.net/syntaxhighlighting/OutliningIndicato
rs/ContractedSubBlock.gif) … {

if (A[right] > A[left])
![](http://images.csdn.net/syntaxhighlighting/OutliningIndicators/ExpandedSubB
lockStart.gif) ![](http://images.csdn.net/syntaxhighlighting/OutliningIndicato
rs/ContractedSubBlock.gif) … {

swap(A[right],A[left]);

![](http://images.csdn.net/syntaxhighlighting/OutliningIndicators/ExpandedSubB
lockEnd.gif) }

return ;
![](http://images.csdn.net/syntaxhighlighting/OutliningIndicators/ExpandedSubB
lockEnd.gif) }

int mid = (right - left) / 2 + left;

MergeLines( & temp[ 0 ], & A[ 0 ],left,mid);

MergeLines( & temp[mid + 1 ], & A[mid + 1 ], 0 ,right - mid -
1 );

// 真正的归并开始（这里可以看做已经做到最后一步）

int k = 0 ;

int i = 0 ,j = mid + 1 ;

while (i <= mid && j <= right)
![](http://images.csdn.net/syntaxhighlighting/OutliningIndicators/ExpandedSubB
lockStart.gif) ![](http://images.csdn.net/syntaxhighlighting/OutliningIndicato
rs/ContractedSubBlock.gif) … {

if (A[i] > A[j])
![](http://images.csdn.net/syntaxhighlighting/OutliningIndicators/ExpandedSubB
lockStart.gif) ![](http://images.csdn.net/syntaxhighlighting/OutliningIndicato
rs/ContractedSubBlock.gif) … {

temp[k ++ ] = A[i ++ ];
![](http://images.csdn.net/syntaxhighlighting/OutliningIndicators/ExpandedSubB
lockEnd.gif) }

else
![](http://images.csdn.net/syntaxhighlighting/OutliningIndicators/ExpandedSubB
lockStart.gif) ![](http://images.csdn.net/syntaxhighlighting/OutliningIndicato
rs/ContractedSubBlock.gif) … {

temp[k ++ ] = A[j ++ ];
![](http://images.csdn.net/syntaxhighlighting/OutliningIndicators/ExpandedSubB
lockEnd.gif) }
![](http://images.csdn.net/syntaxhighlighting/OutliningIndicators/ExpandedSubB
lockEnd.gif) }

if (i > mid)
![](http://images.csdn.net/syntaxhighlighting/OutliningIndicators/ExpandedSubB
lockStart.gif) ![](http://images.csdn.net/syntaxhighlighting/OutliningIndicato
rs/ContractedSubBlock.gif) … {

while (j <= right)
![](http://images.csdn.net/syntaxhighlighting/OutliningIndicators/ExpandedSubB
lockStart.gif) ![](http://images.csdn.net/syntaxhighlighting/OutliningIndicato
rs/ContractedSubBlock.gif) … {

temp[k ++ ] = A[j ++ ];
![](http://images.csdn.net/syntaxhighlighting/OutliningIndicators/ExpandedSubB
lockEnd.gif) }
![](http://images.csdn.net/syntaxhighlighting/OutliningIndicators/ExpandedSubB
lockEnd.gif) }

else
![](http://images.csdn.net/syntaxhighlighting/OutliningIndicators/ExpandedSubB
lockStart.gif) ![](http://images.csdn.net/syntaxhighlighting/OutliningIndicato
rs/ContractedSubBlock.gif) … {

while (i <= mid)
![](http://images.csdn.net/syntaxhighlighting/OutliningIndicators/ExpandedSubB
lockStart.gif) ![](http://images.csdn.net/syntaxhighlighting/OutliningIndicato
rs/ContractedSubBlock.gif) … {

temp[k ++ ] = A[i ++ ];
![](http://images.csdn.net/syntaxhighlighting/OutliningIndicators/ExpandedSubB
lockEnd.gif) }
![](http://images.csdn.net/syntaxhighlighting/OutliningIndicators/ExpandedSubB
lockEnd.gif) }

// 重新将值赋回A数组

for (i = 0 ; i < k;i ++ )
![](http://images.csdn.net/syntaxhighlighting/OutliningIndicators/ExpandedSubB
lockStart.gif) ![](http://images.csdn.net/syntaxhighlighting/OutliningIndicato
rs/ContractedSubBlock.gif) … {

A[i] = temp[i];
![](http://images.csdn.net/syntaxhighlighting/OutliningIndicators/ExpandedSubB
lockEnd.gif) }
![](http://images.csdn.net/syntaxhighlighting/OutliningIndicators/ExpandedBloc
kEnd.gif) }

void All( string pre, char * str, int len) //
pre是前缀，str是真正的串，len是串的长度（除去’/ 0’）
//

//

![](http://images.csdn.net/syntaxhighlighting/OutliningIndicators/ExpandedBloc
kStart.gif) ![](http://images.csdn.net/syntaxhighlighting/OutliningIndicators/
ContractedBlock.gif) … {

if ( * str == ’ / 0 ’ )

return ;

if (len == 1 )
![](http://images.csdn.net/syntaxhighlighting/OutliningIndicators/ExpandedSubB
lockStart.gif) ![](http://images.csdn.net/syntaxhighlighting/OutliningIndicato
rs/ContractedSubBlock.gif) … {

cout << pre << str[ 0 ] << endl;

return ;
![](http://images.csdn.net/syntaxhighlighting/OutliningIndicators/ExpandedSubB
lockEnd.gif) }

for ( int i = 0 ; i < len; i ++ )
![](http://images.csdn.net/syntaxhighlighting/OutliningIndicators/ExpandedSubB
lockStart.gif) ![](http://images.csdn.net/syntaxhighlighting/OutliningIndicato
rs/ContractedSubBlock.gif) … {

if (i == 0 )

All(pre + str[ 0 ], & str[ 1 ],len - 1 );

if (i != 0 )
![](http://images.csdn.net/syntaxhighlighting/OutliningIndicators/ExpandedSubB
lockStart.gif) ![](http://images.csdn.net/syntaxhighlighting/OutliningIndicato
rs/ContractedSubBlock.gif) … {

swap(str[i],str[ 0 ]);

All(pre + str[ 0 ], & str[ 1 ],len - 1 );

swap(str[i],str[ 0 ]);
![](http://images.csdn.net/syntaxhighlighting/OutliningIndicators/ExpandedSubB
lockEnd.gif) }

![](http://images.csdn.net/syntaxhighlighting/OutliningIndicators/ExpandedSubB
lockEnd.gif) }

![](http://images.csdn.net/syntaxhighlighting/OutliningIndicators/ExpandedBloc
kEnd.gif) }

void All( char * List, int currentIndex, int k, int len)
![](http://images.csdn.net/syntaxhighlighting/OutliningIndicators/ExpandedBloc
kStart.gif) ![](http://images.csdn.net/syntaxhighlighting/OutliningIndicators/
ContractedBlock.gif) … {

if (currentIndex == k)
![](http://images.csdn.net/syntaxhighlighting/OutliningIndicators/ExpandedSubB
lockStart.gif) ![](http://images.csdn.net/syntaxhighlighting/OutliningIndicato
rs/ContractedSubBlock.gif) … {

for ( int i = 0 ; i < len; i ++ )
![](http://images.csdn.net/syntaxhighlighting/OutliningIndicators/ExpandedSubB
lockStart.gif) ![](http://images.csdn.net/syntaxhighlighting/OutliningIndicato
rs/ContractedSubBlock.gif) … {

cout << List[i];
![](http://images.csdn.net/syntaxhighlighting/OutliningIndicators/ExpandedSubB
lockEnd.gif) }

cout << endl;
![](http://images.csdn.net/syntaxhighlighting/OutliningIndicators/ExpandedSubB
lockEnd.gif) }

else
![](http://images.csdn.net/syntaxhighlighting/OutliningIndicators/ExpandedSubB
lockStart.gif) ![](http://images.csdn.net/syntaxhighlighting/OutliningIndicato
rs/ContractedSubBlock.gif) … {

for ( int i = currentIndex; i <= k; i ++ )
![](http://images.csdn.net/syntaxhighlighting/OutliningIndicators/ExpandedSubB
lockStart.gif) ![](http://images.csdn.net/syntaxhighlighting/OutliningIndicato
rs/ContractedSubBlock.gif) … {

swap(List[currentIndex],List[i]);

All(List, currentIndex + 1 , k,len);

swap(List[currentIndex],List[i]);

![](http://images.csdn.net/syntaxhighlighting/OutliningIndicators/ExpandedSubB
lockEnd.gif) }
![](http://images.csdn.net/syntaxhighlighting/OutliningIndicators/ExpandedSubB
lockEnd.gif) }

![](http://images.csdn.net/syntaxhighlighting/OutliningIndicators/ExpandedBloc
kEnd.gif) }

void past( int i) // 这里的i是最初的钱的价值（兑换成角，1元就是10角…）不过这里还是使用了穷举…:<
![](http://images.csdn.net/syntaxhighlighting/OutliningIndicators/ExpandedBloc
kStart.gif) ![](http://images.csdn.net/syntaxhighlighting/OutliningIndicators/
ContractedBlock.gif) … {

int u = 0 ;

for ( int j = 0 ; j <= i; j += 5 )

for ( int x = 0 ; x <= i; x += 2 )

for ( int c = 0 ; c <= i;c += 1 )
![](http://images.csdn.net/syntaxhighlighting/OutliningIndicators/ExpandedSubB
lockStart.gif) ![](http://images.csdn.net/syntaxhighlighting/OutliningIndicato
rs/ContractedSubBlock.gif) … {

if (j + x + c == i)
![](http://images.csdn.net/syntaxhighlighting/OutliningIndicators/ExpandedSubB
lockStart.gif) ![](http://images.csdn.net/syntaxhighlighting/OutliningIndicato
rs/ContractedSubBlock.gif) … {

cout << " <5,2,1> " << endl;

cout << j / 5 << " , " << x / 2 << " , " << c << endl;

u ++ ;
![](http://images.csdn.net/syntaxhighlighting/OutliningIndicators/ExpandedSubB
lockEnd.gif) }
![](http://images.csdn.net/syntaxhighlighting/OutliningIndicators/ExpandedSubB
lockEnd.gif) }
![](http://images.csdn.net/syntaxhighlighting/OutliningIndicators/ExpandedBloc
kEnd.gif) }

cLen是srcSet的大小，subSet是符合条件的数据,num是subSet的集合中现含的元素个数。

int match( int * srcSet, int currentIndex, int srcLen, int dest,
int * subSet, int num)
![](http://images.csdn.net/syntaxhighlighting/OutliningIndicators/ExpandedBloc
kStart.gif) ![](http://images.csdn.net/syntaxhighlighting/OutliningIndicators/
ContractedBlock.gif) … {

if (currentIndex == srcLen)

return - 1 ;

if(dest-srcSet[currentIndex] < 0)
return -1;

if (dest - srcSet[currentIndex] == 0 )
![](http://images.csdn.net/syntaxhighlighting/OutliningIndicators/ExpandedSubB
lockStart.gif) ![](http://images.csdn.net/syntaxhighlighting/OutliningIndicato
rs/ContractedSubBlock.gif) … {

subSet[num ++ ] = srcSet[currentIndex];

cout << num << " number match the dest, they are: " << endl;

for ( int i = 0 ; i < num; i ++ )
![](http://images.csdn.net/syntaxhighlighting/OutliningIndicators/ExpandedSubB
lockStart.gif) ![](http://images.csdn.net/syntaxhighlighting/OutliningIndicato
rs/ContractedSubBlock.gif) … {

cout << subSet[i] << " " ;
![](http://images.csdn.net/syntaxhighlighting/OutliningIndicators/ExpandedSubB
lockEnd.gif) }

cout << endl;

return num;
![](http://images.csdn.net/syntaxhighlighting/OutliningIndicators/ExpandedSubB
lockEnd.gif) }

subSet[num] = srcSet[currentIndex];

int number = match(srcSet,currentIndex + 1 ,srcLen,dest -
srcSet[currentIndex],subSet,num + 1 );

if (number <= 0 )
![](http://images.csdn.net/syntaxhighlighting/OutliningIndicators/ExpandedSubB
lockStart.gif) ![](http://images.csdn.net/syntaxhighlighting/OutliningIndicato
rs/ContractedSubBlock.gif) … {

return match(srcSet,currentIndex + 1 ,srcLen,dest,subSet,num);
![](http://images.csdn.net/syntaxhighlighting/OutliningIndicators/ExpandedSubB
lockEnd.gif) }

else
![](http://images.csdn.net/syntaxhighlighting/OutliningIndicators/ExpandedSubB
lockStart.gif) ![](http://images.csdn.net/syntaxhighlighting/OutliningIndicato
rs/ContractedSubBlock.gif) … {

return match(srcSet,currentIndex + 1 ,srcLen,dest,subSet,num);
![](http://images.csdn.net/syntaxhighlighting/OutliningIndicators/ExpandedSubB
lockEnd.gif) }
![](http://images.csdn.net/syntaxhighlighting/OutliningIndicators/ExpandedBloc
kEnd.gif) }