如何找到總結剛剛超過閾值的元素組合

我有一個問題陳述，說：如果你有一個元素{x1，x2，x3，... x10}的數組，找到元素的組合使得它僅僅總計超過閾值（比如閾值爲100）。如何找到總結剛剛超過閾值的元素組合

所以如果存在像x2+x5+x8 = 105,x3+x5+x8=103和x4+x5 = 101這樣的組合，那麼算法應該輸出X4，X5。

揹包算法發出的值接近但低於閾值（這裏爲100）。我想要的是相反的，即大於100的所選元素的最小總和。

是否有任何一組算法或任何可能解決此問題的算法的特例？

2015-10-06 Argho Chatterjee

你可以嘗試改變硬幣改變算法。優化的Coin變化可用於查找O（n）空間中數字數組的所有子集的個別和。但跟蹤哪個子集形成的特定總和是棘手的。看看這個算法的簡化版本[這裏]（http://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/） –

我會首先注意到你要求的最小值嚴格大於某個目標。一般來說，「嚴格大於」和「嚴格小於」約束比「大於或等於」或「小於或等於」約束要困難得多。如果你有所有的整數值，那麼你可以簡單地把你的約束「總和超過100」翻譯成「總和大於或等於101」。我會假設你已經爲剩下的問題做了這樣的轉換。

一種方法是將其視爲整數優化問題，其中每個數字的二元決策變量y_i是否包括它。那麼，我們的目標是儘量減少的數字，它可以模擬爲的總和：

min x_1*y_1 + x_2*y_2 + ... + x_n*y_n

在這種情況下，約束是數字的總和是至少100：

x_1*y_1 + x_2*y_2 + ... + x_n*y_n >= 100

在一般來說，這是一個難題（請注意，它至少與子集總和問題一樣困難，這是NP完全問題）。然而現代優化求解器對於你的問題實例可能是有效的。

要測試的自由解算器的可擴展性對於這個問題，考慮與lpSolve包R（它返回所選擇的子集，如果問題是可行的，NA否則）以下實現：

library(lpSolve) 
min.subset <- function(x, min.sum) { 
    mod <- lp("min", x, matrix(x, nrow=1), ">=", min.sum, all.bin=TRUE) 
    if (mod$status == 0) { 
    which(mod$solution >= 0.999) 
    } else { 
    NA 
    } 
} 
min.subset(1:10, 43.5) 
# [1] 2 3 4 5 6 7 8 9 
min.subset(1:10, 88) 
# [1] NA

要測試可伸縮性，我將從[1, 2, ..., 1000]中隨機選擇n元素，將目標和設置爲元素總和的一半。運行時間爲：

隨着n=100，它在0.01秒內
跑了n=1000，它在0.1秒內
跑了n=10000，它8.7秒跑

看樣子你可以針對超過10k個元素（使用選定的分佈）解決此問題，而不會有太多的計算難題。如果你的問題對於我在這裏使用的免費解算器來說太大了，你可能會考慮Gurobi或者cplex這兩個商業解算器，它們可以免費用於學術用途，但是不是免費的。

來源

2015-10-06 17:24:30 josliber

嘿@Josiber，我試圖在java中實現它，如果你可以提供任何sudo代碼或視頻教程鏈接，對你的實施真的會有所幫助，再次感謝你的努力。 –

@ArghChatterjee我會鼓勵你自己嘗試實現它，併發佈一個新的問題是你碰到任何實現問題。 – josliber

假設X是所有x_i的總和。然後等價地，您要求您的x_i的最小子集總計最多X - 100（因爲這些x_i的補充將是您的問題的最佳解決方案）。所以所有的揹包理論都可以在這裏應用。

在實踐中（真的很大的情況下），我建議this形式的Nemhauser-Ullman泛化，它可以解決數百萬個對象的實例。

來源

2015-10-06 17:44:15 m8mble

如何找到總結剛剛超過閾值的元素組合

回答

相關問題