作者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