题目:给定一个大小为2n的数组，将其分成两个大小为n的数组，要求这两个数组的和的差值尽可能小。
我是不是写过的....记不清了，反正博客没找到，记录一下.
dp[i][j]代表:用i个物品装空间为j能否装的下,true or false
状态转移方程:dp[i][j]=dp[i-1][j-w[k]](如果dp[i-1][j-w[k]]为真)
import java.util.Scanner; public class 数组分割2 { public static void main(String[] args) { Scanner cin=new Scanner(System.in); int n=cin.nextInt(); int a[]=new int[n+1]; int sum=0;//空间总量 for (int i=1;i<=n;i++){ a[i]=cin.nextInt(); sum=sum+a[i]; } boolean dp[][]=new boolean[n+1][sum/2+1];//dp[i][j]代表使用i个物品,能否表示j个空间 dp[0][0]=true; for (int k=1;k<=n;k++){//考虑每一个物品 for (int i=Math.min(k,n/2);i>=1;i--) for (int j=a[k];j<=sum/2;j++) if (dp[i-1][j-a[k]]) dp[i][j]=true;//使用第i个物品,那么考虑i-1个物品表示j-a[i]个空间 } for (int i=sum/2;i>=0;i--){ if (dp[n/2][i]){ System.out.println(i); break; } } cin.close(); } }