如何分佈在水桶元素的數量，使其在一個範圍 - 算法

我已經解決其中說的問題，我有50個元素 n1, n2, n3, ... , n50。如何分佈在水桶元素的數量，使其在一個範圍 - 算法

現在我有有限數量的桶，比如說5桶，桶可以容納的範圍只有100到150（這只不過是該桶中元素的總和），但不能小於100，也不超過150個。

哪種算法最適合解決這個問題，使得所有5個桶都被使用，並且所有元素(n1, n2, n3, ...)也被用完。

如果沒有使用存儲桶或者任何元素被遺漏，則該算法僅返回「InvalidConditionsFound」。

我試過Knapsack，它給了你一個接近Gived編號的組合，但是如何在一個範圍內得到它，並且確保它明智地選擇了所有的桶都被填滿了，而不是那兩個桶被獲取150滿，另一個桶只在50比如說：

來源

2015-10-06 Argho Chatterjee

桶範圍是指必須包含在其中的總和還是該桶中單個數字的範圍？ –

我是否明白只有約束必須被滿足（即每個桶在100到150之間;所有使用的元素），但是沒有必要找到「最佳」解決方案。 – Henry

你有什麼嘗試？它的性能如何，或者它不起作用，在什麼情況下它是越野車？你有代碼嗎？ – Davislor

一種方法是將它建模爲一個整數程序。假設有「m」個數字y_1，y_2，...，y_m和「n」個桶。定義變量x_ij，對於您要分配的每個數字，索引「i」和每個存儲桶的索引「j」。這些是二進制變量，指示每個數字是否分配給每個存儲桶。

現在你有兩套邏輯約束。首先，您需要將每個號碼分配給一個存儲桶。您可以通過添加以下約束每個號碼「我」這樣做：

x_i1 + x_i2 + ... + x_in = 1

您也有關於每個桶「J」的範圍限制：

100 <= y_1 x_1j + y_2 x_2j + ... + y_m x_mj <= 150

真的你只是在尋找任何可行的解決方案，因此您可以將目標設置爲0並將其視爲可行性問題。

當你解決一個NP完全問題，所以這是一個理論上具有挑戰性的練習，你可能會發現現代優化軟件可以解決你感興趣的問題大小的問題。

要了解可擴展性，請考慮使用R中的lpSolve軟件包進行以下實現：

library(lpSolve) 
range.assign <- function(weights, n, min.sum, max.sum) { 
    m <- length(weights) 
    one.mat <- t(sapply(1:m, function(i) c(replicate(n, 1*((1:m) == i))))) 
    w.mat <- t(sapply(1:n, function(j) c(rep(0, m*(j-1)), weights, rep(0, m*(n-j))))) 
    mod <- lp(objective.in = rep(0, n*m), 
      const.mat = rbind(one.mat, w.mat, w.mat), 
      const.dir = rep(c("=", ">=", "<="), c(m, n, n)), 
      const.rhs = rep(c(1, min.sum, max.sum), c(m, n, n)), 
      all.bin=TRUE) 
    if (mod$status == 0) { 
    apply(matrix(mod$solution, nrow=m), 1, function(x) which(x >= 0.999)) 
    } else { 
    rep(NA, m) 
    } 
} 
range.assign(1:5, 2, 5, 10) 
# [1] 1 1 1 1 2 
range.assign(1:5, 2, 5, 6) 
# [1] NA NA NA NA NA

我與m重量從[1, 2, ..., 10]隨機取樣，可接受的範圍剷鬥[100, 150]，和總數測試這樣的：當一個有效的賦值存在，否則返回NA值的矢量，它返回從數字到桶中的分配的水桶n = ceiling(5.5*m/125)。我看到以下運行時換算：

m = 100, n = 5：0.1秒
m = 200, n = 9：0.6秒
m = 300, n = 14：2.2秒
m = 400, n = 18：16。9秒

似乎問題可以用十幾個桶和幾百個權重（以及這個權向量結構）的問題完全使用自由解算器來解決。當然，你的複雜性結果表明它不能有效地解決巨大的問題，但你可能能夠解決你感興趣的大小的實例。進一步優化可以通過以下方式進行：

使用商業求解器，如Gurobi或cplex（兩者都是非免費的，但一般免費供學術使用）。
以稀疏格式輸入約束矩陣。

來源

2015-10-06 11:17:10 josliber

謝謝@Josiber，我會試試這個併發回。 –

嗨@Josiber，我試圖在java中實現它，如果你可以提供任何sudo代碼或視頻教程的鏈接，你的實現將真正幫助完整，再次感謝你的努力。 –

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

聽起來就像其更通常被稱爲bin-packing problem.由於該問題的k劃分問題是NP完全不會有一個「有效」的解決方案。但是，如果你在互聯網上看看，我相信你可以找到大量的代碼示例，所以你和你（*咳嗽*）「同事」可以解決這個問題。

來源

2015-10-06 11:17:17 Glubus

我不相信經典的bin包裝支持分配給每個bin的數量的非零下限，儘管許多變體中的一個允許這些限制。 – josliber

嗨@Glubus，我不明白這是一個簡單的分區問題。你能否詳細解釋一下。 Knapsap是Bin包裝問題的一個特例，如果我沒有錯，那麼你的意思是建議使用Knapsap？我已經實現了它，但它沒有達到 –

問題中提到的場景嘿Argho，我承認我沒有做足夠的研究來給你一個直接的解決方案，你的問題（我目前在我的工作，所以我不能真正得到深入到它）。不過，我覺得您的問題看起來像垃圾箱問題，我期望您可以通過操縱一些現有的解決方案來找到或創建解決方案，以解決不同的問題。我建議您閱讀有關不同問題的問題/解決方案，並確定您是否能夠針對自己的問題推導出解決方案。如果我今晚有時間，我會自己動手。 – Glubus

如何分佈在水桶元素的數量，使其在一個範圍 - 算法

回答

相關問題