Риск ранца, ограниченный решением N-элемента

Question

Этот отрывок из документации CRAN для функции adagio функции knapsack(), как и ожидалось, - решает проблему ранца с вектором прибыли p, весовым вектором w и емкостью cap, выбирая подмножество элементов с максимальной прибылью при условии, что общий вес выбранных элементов не превышает емкость.

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

Как добавить ограничение длины вектора к решению и получить оптимальный ответ? Например, вышеприведенное упражнение, но выбранное подмножество должно содержать ровно три элемента.

Answer 1

Одним из подходов было бы явно моделировать проблему как проблему смешанного целочисленного линейного программирования; Преимущество явного моделирования этого метода заключается в том, что линейные ограничения типа «выбрать ровно три объекта» просты в моделировании. Вот пример с пакетом lpSolve в R, где каждый элемент в задаче о рюкзаке представлен двоичной переменной в смешанной целочисленной формулировке линейного программирования. Требование, чтобы мы выбираем ровно три элемента захватывается ограничение требует переменных решений подводить ровно 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 до нужного размера является разумной эвристикой для случая когда размер требуемого подмножества меньше, чем мощность оптимального решения стандартной проблемы, существуют примеры, когда оптимальное решение стандартной задачи о ранце и оптимальное решение проблемы с размером рюкзака являются непересекающимися. Например, рассмотрим следующую задачу данные:

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 оптимальным решением является выбор двух элементов с прибылью 3 и весом 2, получение общей прибыли 6.