背包算法仅限于N元素解

Question

这个来自adagio函数knapsack()的CRAN文档的摘录按预期运行 - 它解决了利润向量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))

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

Answer 1

一种方法是将问题明确地建模为混合整数线性规划问题; 以这种方式对其进行显式建模的优点是,像"精确挑选三个对象"这样的线性约束很容易建模.下面是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.