2 回答

TA貢獻1895條經驗 獲得超7個贊
如前所述,您的問題實際上是一個受約束的優化問題,對您的數量差異有約束。
在數學上,這將在體積差異小于1000的約束下最小化體積差異。將其表示為線性優化問題的最簡單方法是:
min weights . x
subject to volumes . x < 1000.0
for all i, x[i] = +1 or -1
a . b矢量點積在哪里。解決此問題后,所有索引x = +1對應于您的第一個數組,所有索引x = -1對應于您的第二個數組。
不幸的是,已知0-1整數編程是NP-hard的。解決該問題的最簡單方法是對空間進行窮盡的蠻力探索,但它需要測試所有2^n可能的向量x(n原始weights和volumes向量的長度在哪里),這些向量可能會很快失去控制。關于此主題的文獻很多,算法更為有效,但它們通常針對特定的問題和/或約束條件。您可以在Google上搜索“線性整數編程”,以查看在此主題上所做的事情。
我認為最簡單的方法可能是執行基于啟發式的蠻力搜索,在這種情況下,您會盡早修剪搜索樹,以免超出體積約束,并保持接近約束(一般而言,線性解優化問題在可行空間的邊緣)。
如果您一般不熟悉優化文章或數學知識,那么Wikipedia文章會提供很好的介紹,但是有關此主題的大多數文章會迅速顯示一些您可以立即適應的(偽)代碼。
如果您n
的解決方案很大,我認為您將不得不在解決方案的優化程度與計算速度之間做出權衡。您的解決方案可能不是最佳選擇,但是它比窮舉搜索要快得多。可能會有更好的權衡取舍,具體取決于問題的確切配置。
- 2 回答
- 0 關注
- 307 瀏覽
添加回答
舉報