限於N元件溶液

這摘自CRAN文檔慢板功能揹包（）函數按預期揹包算法 - 它解決了與利潤向量p，權重向量w和容量cap揹包問題，選擇所述子集具有最大利潤的要素受限於選定要素的總重量不超過能力。限於N元件溶液

library(adagio) 
p <- c(15, 100, 90, 60, 40, 15, 10, 1) 
w <- c(2, 20, 20, 30, 40, 30, 60, 10) 
cap <- 102 
(is <- knapsack(w, p, cap))

如何向解決方案添加矢量長度約束並仍然獲得最佳答案？例如，上面的練習，但選定的子集必須包含三個元素。

來源

2016-01-24 Ben Young

一種方法是將問題明確地建模爲混合整數線性規劃問題;以這種方式明確建模它的好處在於，像「精確選擇三個對象」這樣的線性約束很容易建模。下面是R中lpSolve包的一個例子，其中揹包問題中的每個元素都用混合整數線性規劃公式中的二元變量表示。我們選擇正好三個元件的要求是由約束要求決策變量總結準確3.

library(lpSolve) 
p <- c(15, 100, 90, 60, 40, 15, 10, 1) 
w <- c(2, 20, 20, 30, 40, 30, 60, 10) 
cap <- 102 
exact.num.elt <- 3 
mod <- lp(direction = "max", 
      objective.in = p, 
      const.mat = rbind(w, rep(1, length(p))), 
      const.dir = c("<=", "="), 
      const.rhs = c(cap, exact.num.elt), 
      all.bin = TRUE) 
# Solution 
which(mod$solution >= 0.999) 
# [1] 2 3 4 

# Profit 
mod$objval 
# [1] 250

雖然子集劃分從adagio:::knapsack函數的最優解爲所需的大小是拍攝的情況下的合理的啓發式當期望的子集大小小於標準問題的最優解的基數時，存在標準揹包問題的最優解和尺寸約束揹包問題的最優解不相交的示例。例如，考慮下面的問題數據：

p <- c(2, 2, 2, 2, 3, 3) 
w <- c(1, 1, 1, 1, 2, 2) 
cap <- 4 
exact.num.elt <- 2

隨着容量4和沒有尺寸限制，標準揹包問題將選擇利潤2和權重1的四個要素，得到總利潤8。然而，與大小限制2最佳解決方案是選擇利潤3和權重2的兩個元素，獲得總利潤6.

來源

2016-01-24 23:00:19 josliber

限於N元件溶液

回答

相關問題