有没有人使用过 FLSSS R 包中的 mmKnapsack 函数，并收到了次优解决方案？

Question

我刚刚尝试使用 mmKnapsack 函数解决 R 中的多维背包问题。我注意到解决方案似乎有点可疑，所以我尝试了一个非常简单的二维问题：the 2-d problem. It returned an optimal profit of 720, which I can easily see is not the optimal profit of the 2-d problem(the optimal profit is 740). It returns a solution of items 2 and 1 as shown here，但最佳解决方案是第 1、4 和 6 项。 Here是我的代码运行

Answer 1

可能只取决于函数的参数len。例如，如果我运行下面的代码

# packages
library(FLSSS)

# data
prof <- c(400, 320, 230, 210, 190, 130)
costs <- cbind(
  c(6, 3, 2, 2, 2, 1), 
  c(8, 8, 7, 6, 5, 4)
)

capac <- c(9, 18)

然后我得到你当前的最佳解雇

mmKnapsack(
  maxCore = 3, 
  len = 2, 
  itemsProfits = prof, 
  itemsCosts = costs, 
  capacities = capac
)
#> Updated profit = 720
#> $solution
#> [1] 2 1
#> 
#> $selectionCosts
#> [1]  9 16
#> 
#> $budgets
#> [1]  9 18
#> 
#> $selectionProfit
#> [1] 720
#> 
#> $unconstrainedMaxProfit
#> [1] 720

但是如果我增加最大子尺寸（即请注意我设置了 len = 3），我会得到另一个最优解。

mmKnapsack(
  maxCore = 3, 
  len = 3, 
  itemsProfits = prof, 
  itemsCosts = costs, 
  capacities = capac
)
#> Updated profit = 630
#> Updated profit = 660
#> Updated profit = 720
#> Updated profit = 740
#> $solution
#> [1] 6 4 1
#> 
#> $selectionCosts
#> [1]  9 18
#> 
#> $budgets
#> [1]  9 18
#> 
#> $selectionProfit
#> [1] 740
#> 
#> $unconstrainedMaxProfit
#> [1] 950

^{由 reprex package (v0.3.0)}

于 2020 年 3 月 19 日创建

从 package docs 你可以读到，如果你设置 len = 0，那么 FLSSS 函数会尝试寻找所有子集大小的最优解，即

mmKnapsack(
  maxCore = 3, 
  len = 0, 
  itemsProfits = prof, 
  itemsCosts = costs, 
  capacities = capac
)
#> Updated profit = 630
#> Updated profit = 740
#> $solution
#> [1] 1 4 6
#> 
#> $selectionCosts
#> [1]  9 18
#> 
#> $budgets
#> [1]  9 18
#> 
#> $selectionProfit
#> [1] 740
#> 
#> $unconstrainedMaxProfit
#> [1] NA

^{由 reprex package (v0.3.0)}

于 2020 年 3 月 19 日创建

有没有人使用过 FLSSS R 包中的 mmKnapsack 函数，并收到了次优解决方案？

Has anyone used the mmKnapsack function from the FLSSS R package, and received sub-optimal solutions?

optimization

r

knapsack-problem