背包算法仅限于N元解 [英] Knapsack algorithm restricted to N-element solution

问题描述

此摘录来自CRAN文档的adagio函数knapsack()函数按预期方式工作-它解决了利润向量p，权重向量w和容量cap的背包问题，选择了元素子集利润最高的前提是所选元素的总重量不超过容量.

This excerpt from the CRAN documentation for the adagio function knapsack() functions as expected -- it solves the knapsack problem with profit vector p, weight vector w, and capacity cap, selecting the subset of elements with maximum profit subject to the constraint that the total weight of selected elements does not exceed the capacity.

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

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

How can I add a vector length constraint to the solution and still get an optimal answer? For example, the above exercise, but the selected subset must include exactly three elements.

推荐答案

一种方法是将问题明确建模为混合整数线性规划问题.以这种方式显式建模的优点在于，像精确拾取三个对象"这样的线性约束很容易建模.这是R中的lpSolve包的示例，其中背包问题中的每个元素由混合整数线性规划公式中的二进制变量表示.我们选择恰好三个元素的要求是由要求决策变量恰好等于3的约束所满足的.

One approach would be to explicitly model the problem as a mixed integer linear programming problem; the advantage of explicitly modeling it in this way is that linear constraints like "pick exactly three objects" are simple to model. Here is an example with the lpSolve package in R, where each element in the knapsack problem is represented by a binary variable in a mixed integer linear programming formulation. The requirement that we select exactly three elements is captured by the constraint requiring the decision variables to sum to exactly 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函数的最优解子集设置为期望的大小是一种合理的试探法标准背包问题的解决方案与尺寸受限背包问题的最优解决方案不相交.例如，考虑以下问题数据:

While subsetting the optimal solution from the adagio:::knapsack function to the desired size is a reasonable heuristic for the case when the desired subset size is smaller than the cardinality of the optimal solution to the standard problem, there exist examples where the optimal solution to the standard knapsack problem and the optimal solution to the size-constrained knapsack problem are disjoint. For instance, consider the following problem data:

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的情况下，最佳解决方案是选择利润为2的两个元素3和权重2，获得总利润6.

With capacity 4 and no size constraint, the standard knapsack problem will select the four elements with profit 2 and weight 1, getting total profit 8. However, with size limit 2 the optimal solution is instead to select the two elements with profit 3 and weight 2, getting total profit 6.

这篇关于背包算法仅限于N元解的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！