假設我有 N 個物件，每個物件都有關聯的值 A 和 B。這可以表示為元組串列，例如：
[(3,10), (8,4), (0,0), (20,7),...]
其中每個元組都是一個物件，兩個值是 A 和 B。
我想要做的是從這些物件中選擇 M 個（其中 M < N），以使所選子集中的 A 和 B 的總和盡可能平衡。這里的 M 是問題的一個引數，我不想找到最優的 M。我希望能夠說“給我 100 個物件，并讓它們盡可能平衡”。
知道是否有一種有效的演算法可以解決這個問題（不一定是完全最優的）？我認為這可能與裝箱有關，但我不確定。
uj5u.com熱心網友回復：
這是子集和的變體。將每個（A，B）替換為AB，然后所有選定的AB值之和的絕對值就是和的“不平衡度”。所以你真的必須從這些標量中選擇 M 并嘗試使總和盡可能接近 0。
“變體”位是因為您必須準確選擇 M 個專案。（我認為這就是為什么你會想到裝箱而不是子集和的原因。）如果你有一個黑盒子集和求解器，你也可以解釋這一點：如果最大單對絕對差為 D，則替換每個 (A,B) 乘以 (A-B D) 并且目標總和為 M*D。（當然，如果您正在使用動態編程方法，請不要這樣做，因為它會增加您正在使用的數字的大小。）
假設你對一個近似值很好（如果你不是，你會有一個真正糟糕的一天）我傾向于使用模擬退火或延遲接受爬山作為基本方法，從一個貪婪的初始解決方案開始（迭代地添加導致最小差異的任何物件），然后在每一輪中，考慮用一個當前未選擇的物件隨機替換一個物件。
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/409382.html
標籤：
下一篇：Python中的多重集