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

Question

我刚刚尝试使用mmKnapsack函数来解决R中的多维背包问题。我注意到该解决方案似乎有点可疑，因此我尝试了一个非常简单的二维问题：the 2-d problem。它返回了720的最佳利润，我可以很容易地看出它不是二维问题的最佳利润（最佳利润是740）。它返回项目2和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-03-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-03-19创建}