背包算法限于N元解

Question

慢板函数 knapsack() 的 CRAN 文档摘录按预期运行 -- 它解决了利润向量 p、权重向量 w 和容量 [=13] 的背包问题=]，在所选元素的总权重不超过容量的约束条件下，选择利润最大的元素子集

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))

如何在解决方案中添加向量长度约束并仍然获得最佳答案？比如上面的练习，但是选择的子集必须恰好包含三个元素。

Answer 1

一种方法是将问题显式建模为混合整数线性规划问题；以这种方式显式建模的优点是像 "pick exactly three objects" 这样的线性约束易于建模。下面是 R 中 lpSolve 包的示例，其中背包问题中的每个元素都由混合整数线性规划公式中的二进制变量表示。我们 select 恰好三个元素的要求被要求决策变量总和恰好为 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 函数的最佳解决方案子集化为所需大小是一种合理的启发式方法，适用于所需子集大小小于标准问题最佳解决方案的基数的情况，但存在标准背包问题的最优解和 size-constrained 背包问题的最优解不相交的示例。例如，考虑以下问题数据：

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

在容量为 4 且没有尺寸限制的情况下，标准背包问题将 select 利润为 2 且权重为 1 的四个元素得到总利润 8。但是，在尺寸限制为 2 的情况下，最优解是select利润为3，权重为2的两个元素，得到总利润6。

背包算法限于N元解

Knapsack algorithm restricted to N-element solution

r

knapsack-problem

mathematical-optimization