※ 引述《pangfeng (Liu)》之銘言：
: ※ 引述《JonathanWang.bbs@ptt.cc (小尹)》之銘言：
: : 每組最大的數字 加起來 要最小嗎?
: : 那把最小的 p-1 個數字分在 p-1 個組, 剩下其他的數字通通放同一組
: 抱歉中文不是寫的很清楚.
: 每一組數字算出合. 要求P個合中最大的合為最小的分組方法.
[hueristic1]
假設你覺得夠好的解 minmax = k
把所有的值由大到小排好(assume none will be more than k)
每次選p堆中放置目前這個值後不超過k且和最大的一組,來存放目前這個值
最後再視情況調整k值
[heuristic2]
用類似A*的想法,要搜之前先估計往特定方向走會有多好的解
如果只要有可能比較好你就開始搜,那麼就是正解了
而要做的是
[approach1]
用正常方法,但找到夠好的解 (minmax <= k) 就結束
[approach2]
先用別的hueristic找到一個 minmax = k
假設能容忍和正解有d的差距,在搜之前考慮往特定方向走會不會好過 k-d
如果不會就不走了,不然就試一試
其實每一種heuristic都有它自己的弱點,多一點heuristic一起用可能會比較好
--
※ 發信站: 批踢踢兔(ptt2.cc)
◆ From: 218.162.211.251