問題:您將得到一個(gè)整數(shù)權(quán)重列表。您需要將這些權(quán)重分配到兩個(gè)集合中,以使每個(gè)集合的總權(quán)重之間的差異盡可能小。輸入數(shù)據(jù):權(quán)重列表。輸出數(shù)據(jù):一個(gè)數(shù)字,表示可能的最小重量差。我看到了一個(gè)答案,但我不明白為什么bestval = -1。誰能幫我解決這個(gè)問題?多謝!代碼如下:import itertools;def checkio(stones): total = 0 for cur in stones: total += cur bestval = -1 for i in range(0,len(stones)): for comb in itertools.combinations(stones,i): weight = 0 for item in comb: weight += item d = diff(total - weight, weight) if bestval == -1 or d < bestval: bestval = d return bestvaldef diff(a,b): if a >= b: return a - b else: return b - a
2 回答

守候你守候我
TA貢獻(xiàn)1802條經(jīng)驗(yàn) 獲得超10個(gè)贊
bestval最初只是設(shè)置為-1,并且第一次在循環(huán)中更新為d。此后,bestval每次都重新更新,d該值是比current更好的值(也就是較小的權(quán)重差)bestval。
關(guān)鍵代碼在這里...
if bestval == -1 or d < bestval:
bestval = d
因此,在循環(huán)的第一遍中,它bestval == -1是正確的,并且會(huì)bestval被更新。之后,d < bestval檢查將確定是否更新該值。

呼啦一陣風(fēng)
TA貢獻(xiàn)1802條經(jīng)驗(yàn) 獲得超6個(gè)贊
貪婪算法建議是一種很好的啟發(fā)式方法,但絕對(duì)不能保證提供最佳解決方案。這個(gè)問題是NP難的??梢允褂镁植克阉鳎ɡ缒M退火)隨機(jī)地“解決”該問題-解決方案表示“好”答案:一個(gè)被認(rèn)為接近最佳答案的答案??伺梗↘nuth)提出了這個(gè)問題,適用于40個(gè)砝碼和3個(gè)廣口瓶,砝碼等于1..40的平方根。
添加回答
舉報(bào)
0/150
提交
取消