编程之美-数组分割,该如何解决

编程之美--数组分割
有一个没有排序、元素个数为2n的正整数数组，要求：如何能把这个数组分割为元素个数为n的两个数组，
并且使两个子数组的和最接近？
解法三：

C/C++ code


定义：isOK[i][v]表示是否可以找到i个数，使得它们之和等于v
初始化isOK[0][0]=true;
isOK[i][v]=false;(i>0,v>0)
for (int k=1; k<=2*n;++k)
{
    for (int i=min(k,n);i>=1;--i)
    {
        for (int v=1;v<=Sum/2;++v)//Sum是整个数组的和
        {
            if (v>=data[k]&&isOk[i-1][v-data[k]])//data是2n个数的数组
                isOk[i][v] = true;
        }
    }
}

问题是：可以得到最符合的和值v，可是怎么得到是那几个数的和呢？

------解决方案--------------------
看这本书的时候，我直接跳过了这道题。。。呵呵。
------解决方案--------------------
应该就是背包问题了

C/C++ code


vector<int> res[100][1000];
    int main()
    {
        int data[10] = {1,6,88,15,23,64,9,7,5,21};
        int sum = 0;
        for(int i = 0 ; i < 10 ; ++ i)
            sum += data[i];
        int n = 5;
        int isOk[100][1000];
        
        memset(isOk,0,sizeof(isOk));
        isOk[0][0] = 1;
        for (int k=0; k<2*n;++k)
        {
            for (int i=min(k,n);i>=1;--i)
            {
                for (int v=1;v<=sum/2;++v)//Sum是整个数组的和
                {
                    if (v>=data[k]&&isOk[i-1][v-data[k]])//data是2n个数的数组
                    {
                        isOk[i][v] = 1;
                        res[i][v] = res[i-1][v-data[k]];
                        res[i][v].push_back(data[k]);
                    }
                }
            }
        }
        for(int i = sum / 2 ; i >= 0 ; -- i)
        {
            for(int j = 0 ; j < n ; ++ j)
            {
                if(isOk[j][i])
                {
                    cout<<"组合:"
                    copy(res[j][i].begin(),res[j][i].end(),ostream_iterator<int>(cout," "));
                    cout<<endl<<"结果为"<<i<<endl;
                    return 0;
                }
            }
        }
        return 0;
    }

------解决方案--------------------
就是背包问题嘛，接分了。。。

------解决方案--------------------
背包问题。推荐LZ百度一下 背包问题九讲

------解决方案--------------------

这个本质上就是背包思想，楼主的问题是：怎么得到是哪几个数的和呢？？？
这个要想知道是哪几个数的和也是很简单的，只要加上一个while循环，在里面判定当前状态是由哪个状态推导出来的就可以了。。
附上我的代码，给楼主参考一下。。

C/C++ code

#include <iostream>
using namespace std;

//有一个没有排序，元素个数为N的正整数数组。要求把它分割为元素个数为N的两个数组，并使两个子数组的和最接近。

const int N= 2;
int arr[] ={0,3,1, 11,2};
const int SUM = 17;

int splitArray2N_to_N()
{
    int dp[2*N+1][N+1][SUM/2+2];
    /*
    用dp(i,j,c)来表示从前i个元素中取j个、且这j个元素之和不超过c的最佳(大)方案，在这里i>=j,c<=S
    状态转移方程：  
    　　　　　　　　//限第i个物品　　　　　　　不取
            dp(i,j,c)=max{dp(i-1,j-1,c-a[i])+a[i]，dp(i-1,j,c)}
            dp(2N,N,SUM/2+1)就是题目的解
    */ 

    memset(dp,0,sizeof(dp));      //初始化

    for(int i=1;i<=2*N;i++)
    {
        for(int j=1;j<=min(i,N);j++)
        {
            for ( int k= 1; k<= SUM/2+1; ++k)//先赋值,因为如果数组中某个值大于SUM/2+1,则下一个for循环中dp[i][j][s]全,没赋值,错
            {
                dp[i][j][k] = dp[i-1][j][k]; 
            }

            for(int s= SUM/2+1; s>=arr[i]; s--)    //再取其中较大值
            {
                dp[i][j][s] = max(dp[i-1][j-1][s-arr[i]]+arr[i],dp[i-1][j][s]);
            }
        }
    }

    //因为这为最终答案　dp[2*N][N][<SUM/2>];其中<SUM/2>为>=SUM/2的最小整数.(如->4,7->4)
    int iTotalNum=2*N; 
    int j=N;
    int iEven= SUM % 2+ SUM/2;    //如SUM为偶数,则取其一半;如SUM为奇数,则取其一半加1
    int s= iEven;
    cout<<"第一个数组中的元素为:";
    while( iTotalNum > 0 )
    {
        if(dp[iTotalNum][j][s]==dp[iTotalNum-1][j-1][s-arr[iTotalNum]]+arr[iTotalNum])   //判定这个状态是由哪个状态推导出来的
        {
            cout<<arr[iTotalNum]<<" ";   //取出arr[i]
            j--;
            s-=arr[iTotalNum];
        }
        iTotalNum--;
    }
    cout<<endl;
    return dp[2*N][N][iEven];

}

int main(void)
{
    int iSum1= splitArray2N_to_N();    //将一个长度为N的数组分割成个长度为N的数组,且两数组的和的差的绝对值最小,即和最接近
    cout<<"第一个数组的和为:"<< iSum1<<endl;

    system("pause");
    return 0;
}

编程之美-数组分割,该如何解决

相关推荐