プログラミングの美2.18配列分割

本明細書から:http://www.cnblogs.com/freewater/archive/2012/08/23/2652974.html
問題の説明:
ソートされていない要素の数が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に最も近いその和を探し出すことが答えである.このアルゴリズムの時間的複雑さは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という区間のどの値をマークして計算できるかを示す必要がある.
コード:

 1 #include<iostream>

 2 using namespace std;

 3 

 4 int arr[] = {0,1,5,7,8,9,6,3,11,20,17};

 5 const int N = 5;

 6 const int Sum = 87;

 7 

 8 //        0-1       

 9 int solve1()

10 {

11     int i, j, s;

12     int dp[2*N+1][N+1][Sum/2+2];

13     /*

14      dp(i,j,c)     i     j 、  j        c   ( )  ，   i>=j,c<=S

15           ：   

16       i   　　　　　　　  　　

17     dp(i,j,c)=max{dp(i-1,j-1,c-a[i])+a[i]，dp(i-1,j,c)}

18     dp(2N,N,SUM/2+1)      。

19     */

20     //   

21     memset(dp,0,sizeof(dp));

22     for(i = 1 ; i <= 2*N ; ++i)

23     {

24         for(j = 1 ; j <= min(i,N) ; ++j)

25         {

26             for(s = Sum/2+1 ; s >= arr[i] ; --s)

27             {

28                 dp[i][j][s] = max(dp[i-1][j-1][s-arr[i]]+arr[i] , dp[i-1][j][s]);

29             }

30         }

31     }

32 

33     //        　dp[2*N][N][SUM/2+1];

34     i=2*N , j=N , s=Sum/2+1;

35     while(i > 0)

36     {

37         if(dp[i][j][s] == dp[i-1][j-1][s-arr[i]]+arr[i])   //                 

38         {

39             cout<<arr[i]<<" ";    //  arr[i]

40             j--;

41             s -= arr[i];

42         }    

43         i--;

44     }

45     cout<<endl;

46     return dp[2*N][N][Sum/2+1];

47 }

48 

49 int main(void)

50 {

51     int s1 = solve1();

52     cout<<"s1="<<s1<<endl;

53     return 0;

54 }