程式設計之美2.18 數組分割

1.題目描述

• 題目來源：NEU2015年2月月賽，1049

• 題目大意：輸入N，有一個整型數組a[], 裡面有2*N個資料， 将這個數組分成兩個數組，每個數組中有N個數，使這兩個數組的元素和之差最小。

  　　其中：

  1. N<100, 每個資料<100
  2. 輸入以0結尾

2.思路

• 背包問題：從中選取N個數，使它盡量靠近sum/2

• 另一動态規劃的思路：列舉所有N個數可能組成的和

  　　解法：

  　　1. bool flag[i][j] 表示：能否選取i個數使他們的和為j

  　　2. flag初始化為0，flag[0][0] = true

  　　3. 時間複雜度O( n2∗sum )

3.代碼

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

int a[];
bool flag[+][+];

int main()
{
    int n;
    while(scanf("%d",&n) != EOF)
    {
        int sum = ;
        for(int i = ; i<=*n; i++){
            scanf("%d",&a[i]);
            sum += a[i];
        }
        sort(a+, a+n+);
        memset(flag, , sizeof(flag));
        flag[][] = true;
        for(int k = ; k<=*n; k++)
        {
            for(int i = ; i<=k&&i<=n; i++)
            {
                for(int v = ; v<=sum/; v++){
                    if(v >= a[k] && flag[i-][v-a[k]])
                        flag[i][v] = true;
                }
            }
        }
        for(int i = sum/; i>=; i--)
            if(flag[n][i]){
                printf("%d\n",i);
                break;
            }
    }
    return ;
}