[高4]一個(gè)算法問題.

Roadbeg

若由兩個(gè)人 a,b 承擔(dān) n 個(gè)作業(yè)的任務(wù).設(shè) a 處理第 i 個(gè)作業(yè)需時(shí) ai, b 需時(shí) bi.
對(duì)于某些 i ,有 ai>=bi,而 對(duì)于某些 j (i<>j),又有 aj<bj
規(guī)定一個(gè)人不可能同時(shí)處理兩個(gè)任務(wù),一個(gè)任務(wù)也不可能分開由兩個(gè)人完成.
請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法 , 求 a,b 處理 n 的最短時(shí)間及方法.

此題目抄自 2003 年第14期電腦報(bào).

數(shù)據(jù)庫(kù)設(shè)計(jì)時(shí),架構(gòu)思路最重要.
同樣的,編程時(shí)算法最重要,請(qǐng)各位高手出招!

baije

有沒規(guī)定要順次做?
或規(guī)定要同時(shí)完成,
是要合計(jì)時(shí)間最短,
還是要兩人從開始到兩人都結(jié)束的時(shí)間最短?

sunjy

1.數(shù)據(jù)結(jié)構(gòu)

任務(wù)ID        a用時(shí)間      b用時(shí)間      a和b用時(shí)間差(a-b)

  1                a(i)              b(i)             a(i)-b(i)

............................

2.排序，按照 "a和b用時(shí)間差"從大到小排序。

3.從兩頭循環(huán)累加，任務(wù)1開始的循環(huán)累加到變量tb，從任務(wù)n開始的循環(huán)累加到變量ta

循環(huán)中保證ta,tb相差最小。分光所有任務(wù)為止。

  

Trynew

由a在所有任務(wù)中取任意0至n個(gè)的組合，則余下的由b完成，遍歷所有可能的組合，求出兩人相加的時(shí)間為最小即可。其算法與下面貼子相似，只是判斷的條件有所不同:http://www.mzhfr.cn/forum.php?mod=viewthread&tid=28439計(jì)算機(jī)算法通常就是進(jìn)行循環(huán)遍歷所有的可能組合或排列，進(jìn)行比較。

LucasLynn

以下是引用sunjy在2004-6-15 12:56:00的發(fā)言：



1.數(shù)據(jù)結(jié)構(gòu)

任務(wù)ID        a用時(shí)間      b用時(shí)間      a和b用時(shí)間差(a-b)

  1                a(i)              b(i)             a(i)-b(i)

............................

2.排序，按照 "a和b用時(shí)間差"從大到小排序。

3.從兩頭循環(huán)累加，任務(wù)1開始的循環(huán)累加到變量tb，從任務(wù)n開始的循環(huán)累加到變量ta

循環(huán)中保證ta,tb相差最小。分光所有任務(wù)為止。

  

這個(gè)算法應(yīng)該是效率最高的。

LucasLynn

以下是引用Trynew在2005-6-20 10:17:00的發(fā)言：



由a在所有任務(wù)中取任意0至n個(gè)的組合，則余下的由b完成，遍歷所有可能的組合，求出兩人相加的時(shí)間為最小即可。

其算法與下面貼子相似，只是判斷的條件有所不同:

http://www.mzhfr.cn/forum.php?mod=viewthread&tid=28439

計(jì)算機(jī)算法通常就是進(jìn)行循環(huán)遍歷所有的可能組合或排列，進(jìn)行比較。

如果用遍歷，這就不是一道算法題目，而是一個(gè)簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)了。很多情況下，用遍歷的效率會(huì)低得嚇人，比方說這個(gè)例子中，如果N>1000的，用遍歷幾乎不可能在1個(gè)小時(shí)內(nèi)完成計(jì)算。因此計(jì)算機(jī)時(shí)代還是需要我們優(yōu)化算法。ACM精神只有在特定的情況下才適用。

J-2006

[em06]

lxh1968

好好學(xué)習(xí)，天天向上。

open0

it 's asp