Кто-нибудь использовал функцию mmKnapsack из пакета FLSSS R и получил неоптимальные решения? - PullRequest
Новая
       71

Кто-нибудь использовал функцию mmKnapsack из пакета FLSSS R и получил неоптимальные решения?

0 голосов
/ 19 марта 2020

Я только что попытался использовать функцию mmKnapsack для решения многомерной задачи о ранце в R. Я заметил, что решение кажется немного подозрительным, поэтому я попробовал очень простую 2-мерную задачу: 2- проблема d . Он вернул оптимальную прибыль в 720, что, как я вижу, не является оптимальной прибылью для 2-й задачи (оптимальная прибыль - 740). Он возвращает решение пунктов 2 и 1 , как показано здесь , но оптимальным решением являются пункты 1, 4 и 6. Здесь - это код, который я запустил

1 Ответ

0 голосов
/ 19 марта 2020

Возможно, это просто зависит от аргумента 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

Создано в 2020-03-19 с помощью пакета prepx (v0.3.0)

Из документов пакета вы можете прочитать, что если вы установите 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

Создано в 2020-03-19 с помощью представительный пакет (v0.3.0)

...