[网易]和差最小


描述:任意2n个正整数,从其中选出n个整数,使得选出的n个整数和同剩下的n个整数之和的差最小。
来源:网易
已邀请:

sjf0115 - Stay Hungry, Stay Foolish

赞同来自: itfanr 邹博


【方法二】:
【思路】
我们从上面的代码可以看出,S[i][j][k]只与 S[i-1][][]有关,这一点状态方程上也能反映出来。这种固定关系我们可以想办法去掉。从而节省空间。
我们可以用二维数组来代替三维数组来达到降低空间复杂度的目的。
但是怎么代替呢?因为S[i][j][k]只与S[i-1][][]有关,可以把i这一维省略。
同时用二维数组来代替的时候应该对S[i][j][k]的“j”维进行逆序遍历。
为 什么? 因为只有这样才能保证计算S[i][j][k]时利用的S[i-1][j][]和S[i-1][j-1][]是真正i-1这个状态的值,如果正序遍 历,那么当计算S[][j][]时,S[][j-1][]已经变化,那么计算的结果就是错误的。
【代码】
    /*----------------------------------------
    *   日期:2015-02-01
    *   作者:SJF0115
    *   题目: 数组分割
    *   来源:网易
    *   博客:
    --------------------------------------------*/
    #include <iostream>
    #include <cstring>
    #include <algorithm>
    using namespace std;

    int MinSum(int num[],int n){
        if(n <= 0){
            return 0;
        }//if
        int sum = 0;
        int size = 2*n;
        // the sum of all number
        for(int i = 1;i <= size;++i){
            sum += num[i];
        }//for
        int dp[n + 1][sum / 2 + 1];
        // 选中数字路径
        int path[size+1][n + 1][sum / 2 + 1];
        memset(dp,0,sizeof(dp));
        memset(path,0,sizeof(path));
        //
        for(int i = 1;i <= size;++i){
            // 任选j个元素
            int count = min(i,n);
            for(int j = count;j >= 1;--j){
                // 使得其和不超过k且最接近k
                for(int k = num[i-1];k <= sum / 2;++k){
                    if(dp[j][k] < dp[j-1][k-num[i-1]] + num[i-1]){
                        dp[j][k] = dp[j-1][k-num[i-1]] + num[i-1];
                        path[i][j][k] = 1;
                    }//if
                }//for
            }//for
        }//for
        // 打印选择路径
        int i = 2 * n,j = n,k = sum / 2;
        while(i > 0 && j > 0 && k > 0){
            if(path[i][j][k] == 1){
                cout<<num[i]<<" ";
                --j;
                k -= num[i];
            }//if
            --i;
        }//while
        cout<<endl;
        int sum1 = dp[n][sum/2];
        int sum2 = sum - dp[n][sum/2];
        cout<<"Sum1->"<<sum1<<" sum2->"<<sum2<<endl;
        return abs(sum1 - sum2);
    }

    int main(){
        int A[] = {0,1,5,7,8,9,6,3,11,20,17};
        //int A[] = {0,1,2,3,4,5,6,7,8,9,10};
        //int A[] = {0,2,8,5,10};
        int n = 5;
        cout<<"最小差->"<<MinSum(A,n)<<endl;;
        return 0;
    }

要回复问题请先登录注册

收藏七月在线,一起向大牛进阶

ctrl+D或command+D可以快速收藏哦~