Как найти комбинацию элементов, которые суммируются чуть выше порогового значения

Question

У меня есть оператор проблемы, который гласит: если у вас есть массив элементов {x1, x2, x3, ... x10}, найдите комбинацию элементов так что он просто суммируется выше порогового значения (например, пороговое значение равно 100).

Так что если существует такая комбинация, как x2+x5+x8 = 105, x3+x5+x8=103 и x4+x5 = 101, тогда алгоритм должен выводить X4, X5.

Риск ранца испускает значение, которое находится рядом, но на меньшей стороне порога (здесь здесь 100). Я хочу противоположность, то есть наименьшую сумму выбранных элементов, которая больше 100.

Есть ли какой-либо набор алгоритмов или любой частный случай любого алгоритма, который мог бы решить эту проблему?

Answer 1

Начну с того, что вы запрашиваете наименьшее значение, строго превышающее некоторую цель. В общем случае ограничения «строго больше» и «строго меньше» намного сложнее ограничений «больше или равно» или «меньше или равно». Если у вас есть все целочисленные значения, вы можете просто перевести свое ограничение «сумма превышает 100» на «сумма больше или равна 101». Я предполагаю, что вы сделали такое преобразование для остальной части проблемы.

Один из подходов состоит в том, чтобы рассматривать это как проблему оптимизации целочисленного числа, в которой для каждого номера используется двоичная решающая переменная y_i, независимо от того, включаем ли мы ее. Тогда наша цель состоит в том, чтобы минимизировать сумму чисел, которые могут быть смоделированы как:

min x_1*y_1 + x_2*y_2 + ... + x_n*y_n 

Ограничением в данном случае является то, что сумма чисел, по крайней мере 100:

x_1*y_1 + x_2*y_2 + ... + x_n*y_n >= 100 

В вообще это трудная проблема (обратите внимание, что она по крайней мере такая же сложная, как проблема сумм подмножества, полная NP). Однако современные оптимизаторы оптимизации могут быть достаточно эффективными для ваших проблемных экземпляров.

Чтобы проверить масштабируемость свободного решатель для этой проблемы, рассмотрим следующую реализацию с lpSolve пакета в R (она возвращает выбранное подмножество, если проблема возможно и NA иначе):

library(lpSolve) 
min.subset <- function(x, min.sum) { 
    mod <- lp("min", x, matrix(x, nrow=1), ">=", min.sum, all.bin=TRUE) 
    if (mod$status == 0) { 
    which(mod$solution >= 0.999) 
    } else { 
    NA 
    } 
} 
min.subset(1:10, 43.5) 
# [1] 2 3 4 5 6 7 8 9 
min.subset(1:10, 88) 
# [1] NA 

К проверьте масштабируемость, я выберу n элементов случайным образом от [1, 2, ..., 1000], установив целевую сумму на половину суммы элементов. В автономной работы были:

• С n=100, он побежал в 0,01 секунды
• С n=1000, он побежал в 0,1 секунды
• С n=10000, он побежал в 8,7 секунды

Похоже, вы можете решить эту проблему для более чем 10 тыс. элементов (с выбранным распределением) без слишкомких вычислительных задач. Если ваша проблема слишком велика для бесплатного решателя, который я использовал здесь, вы можете рассмотреть Gurobi или cplex, два коммерческих решателя, которые бесплатны для академического использования, но в противном случае не являются бесплатными.

Answer 2

Предположим, X - это сумма всех x_i.Тогда эквивалентно, вы запрашиваете минимальное подмножество своего x_i, которое суммирует не более чем до X - 100 (в качестве дополнения к этим x_i будет оптимальным решением вашей проблемы). Таким образом, всякая теория Кнапсака может быть применена здесь.

На практике (действительно большие экземпляры), я бы предложил this форму обобщения Nemhauser-Ullman, которая может разрешать экземпляры с миллионами объектов.