[高4]一個算法問題.

Roadbeg

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

此題目抄自 2003 年第14期電腦報.

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

baije

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

sunjy

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

任務ID        a用時間      b用時間      a和b用時間差(a-b)

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

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

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

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

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

  

Trynew

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

LucasLynn

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



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

任務ID        a用時間      b用時間      a和b用時間差(a-b)

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

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

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

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

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

  

這個算法應該是效率最高的。

LucasLynn

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



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

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

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

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

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

J-2006

[em06]

lxh1968

好好學習，天天向上。

open0

it 's asp