[討論] 整數陣列限定總和與上下界,取亂數值
看板Prob_Solve (計算數學 Problem Solving)作者tropical72 (藍影)時間13年前 (2011/10/20 03:18)推噓0(0推 0噓 7→)留言7則, 2人參與討論串1/4 (看更多)
抱歉，標題我想半天我還是不知道該怎麼說明，看完題目若知屬什麼問題，
請不吝告知，將更改為較合題意之標題，謝謝。
實際問題如下敘述
一陣列裡有 n 個整數元素，假設為 arr[n]，若對每個 arr[i] 取亂數，
每個 arr[i] 又有個自之上、下界，假設分別為 low[i] 與 up[i]，
(故 low 與 up 也是有 n 個整數元素 )，同時限定此陣列之總和剛好為 sum，
即 arr[0] + arr[1] + ...arr[n] = sum。其中 sum 保證介於
low[0] + low[1] + .... + low[n-1] 與
up[0] + up[1] + .... + up[n-1] 之間，
試問該如何決定陣列 arr 內之元素？
我嘗試的解法如下 (獻醜了)
演算法大致如下所述
process:
assign low to arr
slack = sum - (sum of low array)
for i:= 1 to slack
* cal column prob. of (range of up[j],arr[j]) (prob[j])
* generate rnd = random(0,1)
* find min j , st prob[j] >= rnd
* increment arr[j]
end for
end process
可能沒寫那麼清楚，提供小弟 website 上詳細說明
http://edisonx.pixnet.net/blog/post/81995873
website 裡我自提到，當 sum of (up[i] - low[i]) 很大時，
執行時間會拉大，但考慮了甚多問題後，乃覺得這方式最為穩定、簡易，
殊不知是否有其它解決方案？
不知各位版友對於此問，或小弟嚐試之作法有無意見，或想法可供參考，
小弟感激不盡。
--
No matter how gifted you are,
alone, can not change the world.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
※ 編輯: tropical72 來自: 180.177.78.41 (10/20 03:39)
→
10/20 07:40, , 1F
10/20 07:40, 1F
→
10/20 07:40, , 2F
10/20 07:40, 2F
→
10/20 07:40, , 3F
10/20 07:40, 3F
→
10/20 09:20, , 4F
10/20 09:20, 4F
→
10/21 21:00, , 5F
10/21 21:00, 5F
→
10/21 21:56, , 6F
10/21 21:56, 6F
→
10/21 21:56, , 7F
10/21 21:56, 7F
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1 之 4 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
-1
12