• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            為生存而奔跑

               :: 首頁 :: 聯(lián)系 :: 聚合  :: 管理
              271 Posts :: 0 Stories :: 58 Comments :: 0 Trackbacks

            留言簿(5)

            我參與的團隊

            搜索

            •  

            積分與排名

            • 積分 - 330222
            • 排名 - 74

            最新評論

            閱讀排行榜

            評論排行榜

            題目概述:有一個沒有排序,元素個數(shù)為2N的正整數(shù)數(shù)組。要求把它分割為元素個數(shù)為N的兩個數(shù)組,并使兩個子數(shù)組的和最接近。
            假設(shè)數(shù)組A[1..2N]所有元素的和是SUM。模仿動態(tài)規(guī)劃解0-1背包問題的策略,令S(k, i)表示前k個元素中任意i個元素的和的集合。顯然:
            S(k, 1) = {A[i] | 1<= i <= k}
            S(k, k) = {A[1]+A[2]+…+A[k]}
            S(k, i) = S(k-1, i) U {A[k] + x | x屬于S(k-1, i-1) }
            按照這個遞推公式來計算,最后找出集合S(2N, N)中與SUM最接近的那個和,這便是答案。這個算法的時間復(fù)雜度是O(22N).
            因為這個過程中只關(guān)注和不大于SUM/2的那個子數(shù)組的和。所以集合中重復(fù)的和以及大于SUM/2的和都是沒有意義的。把這些沒有意義的和剔除掉,剩下的有意義的和的個數(shù)最多就是SUM/2個。所以,我們不需要記錄S(2N,N)中都有哪些和,只需要從SUM/2到1遍歷一次,逐個詢問這個值是不是在S(2N,N)中出現(xiàn),第一個出現(xiàn)的值就是答案。我們的程序不需要按照上述遞推公式計算每個集合,只需要為每個集合設(shè)一個標志數(shù)組,標記SUM/2到1這個區(qū)間中的哪些值可以被計算出來。關(guān)鍵代碼如下:

            for(i = 0; i < N+1; i++)  
                for(j = 0; j < sum/2+1; j++)  
                    flag[i][j] = false;  
            flag[0][0] = true;  
            for(int k = 1; k <= 2*N; k++) {  
                for(i = k > N ? N : k; i >= 1; i--) {  
                    //兩層外循環(huán)是遍歷集合S(k,i)  
                    for(j = 0; j <= sum/2; j++) {  
                        if(j >= A[k] && flag[i-1][j-A[k]])  
                            flag[i][j] = true;  
                    }  
                }  
            }  
            for(i = sum/2; i >= 0; i--) {  
                if(flag[N][i]) {  
                    cout << "minimum delta is " << abs(2*i - sum) << endl;  
                    break;  
                }  
            posted on 2009-08-06 10:07 baby-fly 閱讀(6568) 評論(3)  編輯 收藏 引用 所屬分類: Algorithm

            Feedback

            # re: 數(shù)組分割問題 2009-09-24 10:31 upwill
            那怎么輸出那兩個子數(shù)組呢?  回復(fù)  更多評論
              

            # re: 數(shù)組分割問題 2009-11-11 21:50 wacuum
            設(shè)置前驅(qū),說明這個值是由哪個元素跟前面哪個值一起產(chǎn)生的  回復(fù)  更多評論
              

            # re: 數(shù)組分割問題 2013-09-06 09:06 呵呵
            轉(zhuǎn)載請注明  回復(fù)  更多評論
              

            久久久久久精品成人免费图片| 91久久精品电影| 午夜人妻久久久久久久久| 香蕉久久av一区二区三区| 青青草原综合久久| 思思久久精品在热线热| 日产精品久久久一区二区| 成人精品一区二区久久久| 久久青青草视频| 免费国产99久久久香蕉| 久久久亚洲AV波多野结衣| 久久精品成人免费网站| 日本WV一本一道久久香蕉| 久久99国产精品一区二区| 中文字幕无码精品亚洲资源网久久| 狠狠狠色丁香婷婷综合久久五月| 亚洲欧美一级久久精品| 99久久久久| 久久精品国产99国产精品| 狠狠狠色丁香婷婷综合久久五月| 麻豆精品久久久久久久99蜜桃 | 国产精品xxxx国产喷水亚洲国产精品无码久久一区 | 久久婷婷五月综合97色直播| 99久久人人爽亚洲精品美女| 日日噜噜夜夜狠狠久久丁香五月| 久久国产午夜精品一区二区三区| 国产综合久久久久久鬼色| 久久精品国产精品亚洲精品| 亚洲国产成人久久综合一区77| 国产精品99久久久久久www| 久久久精品一区二区三区| 97久久超碰国产精品旧版| 无码人妻久久一区二区三区| 99精品久久精品一区二区| A级毛片无码久久精品免费| 伊人久久国产免费观看视频| 欧美日韩中文字幕久久久不卡| 久久精品国产只有精品66| 激情五月综合综合久久69| 97精品国产97久久久久久免费| 国产精品久久久天天影视|