問題：
1. 有一個無序、元素個數為2n的正整數數組，要求：如何能把這個數組分割為兩個子數組，子數組的元素個數不限，並使兩個子數組之和最接近。
2. 有一個無序、元素個數為2n的正整數數組，要求：如何能把這個數組分割為元素個數為n的兩個數組，並使兩個子數組之和最接近。
ps: 這只是我對該問題解法的理解，其實感覺還是有點變扭的，如有更好的思考方式，希望告知，謝謝。
1. 解法：
由於對兩個子數組和最接近的判斷不太直觀，我們需要對題目進行適當轉化。我們知道當一個子數組之和最接近原數組之和sum的一半時，兩個子數組之和是最接近的。所以轉化後的題目是：從2n個數中選出任意個數，其和盡量接近於給定值sum/2。
這個問題存儲的是從前k個數中選取任意個數，且其和為s的取法是否存在dp[k][s]。之所以將選出的數之和放在下標中，而不是作為dp[k]的值，是因為那種做法不滿足動態規劃的前提——最優化原理，假設我們找到最優解有k個數（選出的這k個數之和是最接近sum/2的），但在所有k-1數之和中的最優解的前k-1個數之和可能並不是最接近sum/2的，即最優解的子問題並不是最優的，所以不滿足最優化原理。因此我們需要將dp[k]的值作為下標存儲起來，將這個最優問題轉化為判定問題，用帶動態規劃的思想的遞推法來解。
外階段：在前k1個數中進行選擇，k1=1,2...2*n。
內階段：從這k1個數中任意選出k2個數，k2=1,2...k1。
狀態：這k2個數的和為s，s=1,2...sum/2。
決策：決定這k2個數的和有兩種決策，一個是這k2個數中包含第k1個數，另一個是不包含第k1個數。
dp[k][s]表示從前k個數中取任意個數，且這些數之和為s的取法是否存在。
[cpp]
#include <iostream>
#include <algorithm>
using namespace std;
#define MAXN 101
#define MAXSUM 100000
int A[MAXN];
bool dp[MAXN][MAXSUM];
// dp[k][s]表示從前k個數中去任意個數，且這些數之和為s的取法是否存在
int main()
{
int n, i, k1, k2, s, u;
cin >> n;
for (i=1; i<=2*n; i++)
cin >> A[i];
int sum = 0;
for (i=1; i<=2*n; i++)
sum += A[i];
memset(dp,0,sizeof(dp));
dp[0][0]=true;
// 外階段k1表示第k1個數，內階段k2表示選取數的個數
for (k1=1; k1<=2*n; k1++) // 外階段k1
{
for (k2=k1; k2>=1; k2--) // 內階段k2
for (s=1; s<=sum/2; s++) // 狀態s
{
//dp[k1][s] = dp[k1-1][s];
// 有兩個決策包含或不包含元素k1
if (s>=A[k1] && dp[k2-1][s-A[k1]])
dp[k2][s] = true;
}
}
// 之前的dp[k][s]表示從前k個數中取任意k個數，經過下面的步驟後
// 即表示從前k個數中取任意個數
for (k1=2; k1<=2*n; k1++)
for (s=1; s<=sum/2; s++)
if (dp[k1-1][s]) dp[k1][s]=true;
// 確定最接近的給定值sum/2的和
for (s=sum/2; s>=1 && !dp[2*n][s]; s--);
printf("the differece between two sub array is %d\n", sum-2*s);
}
2. 解法：www.2cto.com
但本題還增加了一個限制條件，即選出的物體數必須為n，這個條件限制了內階段k2的取值范圍，並且dp[k][s]的含義也發生變化。這裡的dp[k][s]表示從前k個數中取任意不超過n的k個數，且這些數之和為s的取法是否存在。
[cpp]
#include <iostream>
#include <algorithm>
using namespace std;
#define MAXN 101
#define MAXSUM 100000
int A[MAXN];
bool dp[MAXN][MAXSUM];
// 題目可轉換為從2n個數中選出n個數，其和盡量接近於給定值sum/2
int main()
{
int n, i, k1, k2, s, u;
cin >> n;
for (i=1; i<=2*n; i++)
cin >> A[i];
int sum = 0;
for (i=1; i<=2*n; i++)
sum += A[i];
memset(dp,0,sizeof(dp));
dp[0][0]=true;
// 對於dp[k][s]要進行u次決策，由於階段k的選擇受到決策的限制，
// 這裡決策選擇不允許重復，但階段可以重復，比較特別
for (k1=1; k1<=2*n; k1++) // 外階段k1
for (k2=min(k1,n); k2>=1; k2--) // 內階段k2
for (s=1; s<=sum/2; s++) // 狀態s
// 有兩個決策包含或不包含元素k1
if (s>=A[k1] && dp[k2-1][s-A[k1]])
dp[k2][s] = true;
// 確定最接近的給定值sum/2的和
for (s=sum/2; s>=1 && !dp[n][s]; s--);
printf("the differece between two sub array is %d\n", sum-2*s);
}
