プログラマー面接100題の15:配列分割

一、タイトルの概要:ソートされていない要素の個数が2 Nの正の整数配列がある.要素個数Nの2つの配列に分割し,2つのサブ配列の和を最も近づけることが要求される.配列A[1.2 N]のすべての要素の和がSUMであると仮定する.動的計画解0−1リュック問題の戦略を模倣し,S(k,i)に前のk要素のうち任意のi要素の和の集合を表す.明らかに、S(k,1)={A[i]|1<=i<=k}S(k,k)={A[1]+A[2]+…+A[k]}S(k,i)=S(k−1,i)U{A[k]+x|xはS(k−1,i−1)}この繰返し式に従って計算し、最後に集合S(2 N,N)の中でSUM/2に最も近い和を探し出すことが答えである.このアルゴリズムの時間複雑度はO(2^N)である.この過程ではSUM/2以下のサブ配列の和のみが注目されるからである.したがって,集合中の和がSUM/2より大きい和は意味がない.これらの意味のない和を除いて、残りの意味のある和の個数はSUM/2個までです.したがって,S(2 N,N)にどのような和があるかを記録する必要はなく,SUM/2から1まで1回遍歴し,この値がS(2 N,N)に現れるかどうかを1つずつ尋ね,最初に現れる値が答えである.我々のプログラムでは,上記の繰返し式に従って各集合を計算する必要はなく,各集合にフラグ配列を設け,SUM/2から1という区間のどの値をマークして計算できるかを示す必要がある.キーコードは次のとおりです.

#include<iostream>
using namespace std;

//       ，     2N      。            N     ，            。
int arr[] = {0,1,5,7,8,9,6,3,11,20,17};
const int N=5;
const int SUM = 87;

//        0-1       
int solve1()
{
	int i , j , s;
	int dp[2*N+1][N+1][SUM/2+2];

	/*
	 dp(i,j,c)     i     j 、  j        c   ( )  ，   i>=j,c<=S
	      ：   
	  i   　　　　　　　  　　
	dp(i,j,c)=max{dp(i-1,j-1,c-a[i])+a[i]，dp(i-1,j,c)}
	dp(2N,N,SUM/2+1)      。
	*/
	//   
	memset(dp,0,sizeof(dp));

	for(i = 1 ; i <= 2*N ; ++i)
	{
		for(j = 1 ; j <= min(i,N) ; ++j)
		{
			for(s = SUM/2+1 ; s >= arr[i] ; --s)
			{
				dp[i][j][s] = max(dp[i-1][j-1][s-arr[i]]+arr[i] , dp[i-1][j][s]);
			}
		}
	}

	//        　dp[2*N][N][SUM/2+1];
	i=2*N , j=N , s=SUM/2+1;
	while(i > 0)
	{
		if(dp[i][j][s] == dp[i-1][j-1][s-arr[i]]+arr[i])   //                 
		{
			cout<<arr[i]<<" ";    //  arr[i]
			j--;
			s -= arr[i];
		}	
		i--;
	}
	cout<<endl;
	return dp[2*N][N][SUM/2+1];
}

int solve2()
{
	int i , j , s;
	int dp[N+1][SUM/2+2];     // Ｎ+１   ，     SUM/2+2，        
	memset(dp,0,sizeof(dp));    //      0

	for(i = 1 ; i <= 2*N ; ++i)
	{
		for(j = 1 ; j <= min(i,N) ; ++j)
		{
			for(s = SUM/2+1 ; s >= arr[i] ; --s)    //01      ，     ，       
			{
				dp[j][s] = max(dp[j-1][s-arr[i]]+arr[i] , dp[j][s]); 
			}
		}
	}
	//      　      ，
	return dp[N][SUM/2+1];
}

int solve3()
{
	int i , j , s;
	int isOK[N+1][SUM/2+2]; //isOK[i][v]        i  ，        v
	memset(isOK,0,sizeof(isOK));    //    
	//     
	isOK[0][0] = 1; //  , 0   ，   0，    

	for(i = 1 ; i <= 2*N ; ++i)
	{
		for( j = 1 ; j <= min(i,N) ; ++j)
		{
			for(s = SUM/2+1 ; s >= arr[i] ; --s) //    ，      
			{
				if( isOK[j-1][s-arr[i]] )
					isOK[j][s] = 1;
			}
		}
	}
	for(s = SUM/2+1 ; s >= 0 ; --s)
	{
		if(isOK[N][s])
			return s;
	}

	//            
	return 0;
}

int main(void)
{
	int s1 = solve1();
	int s2 = solve2();
	int s3 = solve3();
	cout<<"s1="<<s1<<endl;
	cout<<"s2="<<s2<<endl;
	cout<<"s3="<<s3<<endl;
	system("pause");
	return 0;
}

二、
拡張問題:2つの配列要素を交換して、2つの配列の和の差を最小限に抑える
2つの配列a、bがあり、大きさはいずれもnであり、配列要素の値は任意の整形数であり、無秩序である.要求:a、b配列の要素を交換することによって、[配列a要素の和]と[配列b要素の和]の差を最小限に抑える.
実はこの問題は上の問題の変形で、a、bの2つの配列を1つの配列に結合して、それから問題は2*nの要素配列を2つの長さnの配列に分割して、そして2つのサブ配列の和を最も近づけることに転化します.また、特に注意:配列に負数がある場合は、上のリュックストラテジーは使用できません(第3サイクルのsは配列の下付きとして負数が出ないため)、配列のすべての配列に最小のその負数の絶対値を加え、配列の要素をすべて一定の範囲増やし、すべて正数に変換する必要があります.そして上のリュックサック戦略を使えば解決できます.