仅限于 N 元解的背包算法

这段摘自 CRAN 文档的 adagio 函数 knapsack() 的功能符合预期——它用利润向量解决了背包问题p，权重向量w，和容量cap，在所选元素的总权重不超过容量的约束下，选择利润最大的元素子集。

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

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

一种方法是将问题显式建模为混合整数线性规划问题；以这种方式显式建模的优点是，像“恰好选择三个对象”这样的线性约束很容易建模。下面是 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 的两个元素2、获得利润总额6。