将数组分成两组，使两组的和的差的绝对值最小-ag真人游戏

数组中的数分为两组，给出一个算法，使得两个组的和的差的绝对值最小数组中的数的取值范围是0
比如a[]={2,4,5,6,7},得出的两组数{2，4,，6}和{5，7}，abs(sum(a1)-sum(a2))=0; 

比如{2，5，6，10}，abs(sum(2,10)-sum(5,6))=1,所以得出的两组数分别为{2，10}和{5,，6}。  

初看问题，感觉好像是个组合问题，通过暴力穷举解决问题。

但仔细想想，问题可以转换成，从数组中找出一组数据，使之尽可能等于数组和的一半。

这样一来是不是有点类似于0-1背包呢？是的，就是0-1背包问题。

条件：数组中的数就是背包问题的weight值，数组中的数也是背包问题的value值，即二者一样。

问题：背包里装哪些物品，使得其价值之和最接近总价值的一半。

于是通过背包问题来解决这道题就显得很简单了，下面简单陈述通过动态规划来求解0-1背包问题的思路。

假设v[i][j]表示从i件物品中选出重量为j的物品的最大价值,weight[i],value[i]分别代表第i件物品的重量和价值（在题目中，weight、value属于同一数组）。

动态转移方程为:

v[i][j]=v[i-1][j]  if j

v[i][j]=max(v[i-1][j],v[i-1][j-weight[i]] value[i]) if j>weight[i]

另外，如果想知道是由那几件物品组成的最大价值，可以从后往前回溯，当v[i][j]>v[i-1][j],说明第i件物品被加入（路径不唯一）。

#include 
#include 
using namespace std;
int knapsack(int num,int c,const vector weight,const vector value,vector &x);
int main()
{
    int w[]={2,4,5,6,7};
    int v[]={2,4,5,6,7};
    int num=sizeof(w)/sizeof(w[0]);
    vector weight(w,w num);
    vector value(v,v num);
    int c=12;
    vector x(num);
    int total=knapsack(num,c,weight,value,x);
    cout<<"total weight is "< weight,const vector value,vector &x){
    vector > v(num 1,vector(c 1));
    for(int i=1;i<=num;i  ){
        for(int j=1;j<=c;j  ){
            if(j0;i--){
        if(v[i][j]>v[i-1][j]){
            x[i]=1;
            j=j-weight[i-1];
        }
        else
            x[i]=0;
    }
    cout<<"the articles chosen is: "<