TA貢獻(xiàn)1876條經(jīng)驗(yàn) 獲得超7個(gè)贊
先將石頭按質(zhì)量從大到小放到數(shù)組stone[0]~stone[99]中。然后對(duì)A、B兩個(gè)組按貪心法進(jìn)行選擇：
1、讓A先?。?br/>2、循環(huán)進(jìn)行剩下的99次選取，每次選取時(shí)，總重量小的具有選取權(quán)。
具體過(guò)程描述可如下：
//前提條件：數(shù)組stone中從大到小存放了100個(gè)數(shù)。
list listA, listB;
list *p;
listA.Insert(stone[0]);
for(int i = 1; i < 100; i++) {
p = listA.Sum( ) < listB.Sum( ) ? &listA : &listB;
*p.Insert(stone[i]);
}
TA貢獻(xiàn)1802條經(jīng)驗(yàn) 獲得超5個(gè)贊
這是一個(gè)典型的動(dòng)態(tài)規(guī)劃里面的數(shù)組分割問(wèn)題。
給你找出來(lái)一個(gè)可以作為類(lèi)比的題目，其實(shí)實(shí)質(zhì)是一模一樣的：
題目概述：有一個(gè)沒(méi)有排序，元素個(gè)數(shù)為2N的正整數(shù)數(shù)組。要求把它分割為元素個(gè)數(shù)為N的兩個(gè)數(shù)組，并使兩個(gè)子數(shù)組的和最接近。
假設(shè)數(shù)組A[1..2N]所有元素的和是SUM。模仿動(dòng)態(tài)規(guī)劃解0-1背包問(wèn)題的策略，令S(k, i)表示前k個(gè)元素中任意i個(gè)元素的和的集合。顯然：
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) }
按照這個(gè)遞推公式來(lái)計(jì)算，最后找出集合S(2N, N)中與SUM最接近的那個(gè)和，這便是答案。這個(gè)算法的時(shí)間復(fù)雜度是O(22N).
因
為這個(gè)過(guò)程中只關(guān)注和不大于SUM/2的那個(gè)子數(shù)組的和。所以集合中重復(fù)的和以及大于SUM/2的和都是沒(méi)有意義的。把這些沒(méi)有意義的和剔除掉，剩下的有
意義的和的個(gè)數(shù)最多就是SUM/2個(gè)。所以，我們不需要記錄S(2N,N)中都有哪些和，只需要從SUM/2到1遍歷一次，逐個(gè)詢(xún)問(wèn)這個(gè)值是不是在
S(2N,N)中出現(xiàn)，第一個(gè)出現(xiàn)的值就是答案。我們的程序不需要按照上述遞推公式計(jì)算每個(gè)集合，只需要為每個(gè)集合設(shè)一個(gè)標(biāo)志數(shù)組，標(biāo)記SUM/2到1這
個(gè)區(qū)間中的哪些值可以被計(jì)算出來(lái)。關(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;
}
}
舉報(bào)