knapsack() 向量长度问题

Question

当我运行

weights <- 1:50
profits <- 1:50
library(adagio)
knapsack(w = weights, p = profits, cap = 30)

我收到错误

Error in F[, k] <- G : 
  number of items to replace is not a multiple of replacement length
In addition: Warning message:
In pmax(G, H) : an argument will be fractionally recycled

但是当我运行更小的向量时，比如

weights <- 1:20
profits <- 1:20
knapsack(w = weights, p = profits, cap = 30)

运行没问题。 knapsack() 是否只是为了更大的集合而减速（并防止运行ning）？我希望最终使用数千个长度。

Answer 1

这是传递重量超过总容量的元素的问题。要查看问题，让我们看一下 knapsack 函数的前几行：

function (w, p, cap) 
{
    n <- length(w)
    x <- logical(n)
    F <- matrix(0, nrow = cap + 1, ncol = n)
    G <- matrix(0, nrow = cap + 1, ncol = 1)
    for (k in 1:n) {
        F[, k] <- G
        H <- c(numeric(w[k]), G[1:(cap + 1 - w[k]), 1] + p[k])
        G <- pmax(G, H)
    }

当迭代地一次填充 F 矩阵一列时，该算法使用以下命令创建向量 H（然后立即计算 pmax(G, H)）：

H <- c(numeric(w[k]), G[1:(cap + 1 - w[k]), 1] + p[k])

numeric(w[k]) 的长度为 w[k]，当 w[k] <= cap、G[1:(cap + 1 - w[k]), 1] + p[k] 的长度为 cap + 1 - w[k] 时，意味着整个向量的长度为 H cap+1，匹配 G 的大小。另一方面，当 w[k] == cap + 1 时，我们将得到一个大小为 cap+2 的 H 向量，它与 G 的大小不匹配，这给我们带来了麻烦，并且使用 w[k] > cap + 1 我们将得到混合正负索引的错误。

回到您的示例函数调用，您的权重高达 50，但容量只有 30，产生错误：

weights <- 1:50
profits <- 1:50
knapsack(w = weights, p = profits, cap = 30)
# Error in F[, k] <- G : 
#   number of items to replace is not a multiple of replacement length
# In addition: Warning message:
# In pmax(G, H) : an argument will be fractionally recycled

然而，当您限制重量不超过容量的元素时，您不会收到任何错误：

knapsack(w = weights[weights <= 30], p = profits[weights <= 30], cap = 30)
# $capacity
# [1] 30
# 
# $profit
# [1] 30
# 
# $indices
# [1] 1 2 3 4 5 7 8

如果 knapsack 函数优雅地删除任何重量超过容量的对象（因为在可行的解决方案中永远不会使用此类元素）并为您的代码提供解决方案，那将是最理想的已发布，但作为解决方法，您可以自己将它们从 knapsack 函数的输入中删除。

Answer 2

我收到了同样的错误（这就是我如何得到这个 SO post..）我认为 adagio knapsack 函数不喜欢分数值的利润或权重。我使用 rnorm() 生成利润和权重，将它们的结果与我个人编写的另一个背包函数进行比较。即使容量比所有重量加起来大几倍，我也会收到 'recycling' 错误。但是，当我在将 rnorm() 向量作为参数传递给 knapsack 之前对其进行四舍五入时，没问题。

knapsack() 向量长度问题

knapsack() vector length issues

r

knapsack-problem

mathematical-optimization