作者tropical72 (藍影)
站內Prob_Solve
標題[討論] 整數陣列限定總和與上下界,取亂數值
時間Thu Oct 20 03:18:21 2011
抱歉，標題我想半天我還是不知道該怎麼說明，看完題目若知屬什麼問題，
請不吝告知，將更改為較合題意之標題，謝謝。
實際問題如下敘述
一陣列裡有 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)
1F：→ AmosYang:這個題目本身與你的解法…很難寫成 paper 10/20 07:40
2F：→ AmosYang:但如果你能 *證明* 你的方法能產生最好的 randomness , 10/20 07:40
3F：→ AmosYang:這個“證明的方法”或許會有學術價值且寫成 paper 10/20 07:40
4F：→ tropical72:謝謝 A 大建議, 其實比較想知道還能怎更快, 感謝 10/20 09:20
5F：→ AmosYang: 求快之前要先求正確啊 XD 10/21 21:00
6F：→ tropical72:是啊!提出的 algorithm 都有問題,還在想怎樣方式兼具有 10/21 21:56
7F：→ tropical72:效性與正確性. XD 10/21 21:56