Как распределить количество элементов в ведре так, чтобы оно было в пределах диапазона — алгоритм

Одним из подходов было бы смоделировать это как целочисленную программу. Предположим, что есть "m" чисел y_1, y_2,..., y_m и "n" сегментов. Определите переменные x_ij с индексом «i» для каждого из чисел, которые вы пытаетесь присвоить, и индексом «j» для каждого сегмента. Это двоичные переменные, указывающие, присвоено ли каждому сегменту каждое число.

Теперь у вас есть два набора логических ограничений. Во-первых, вам нужно присвоить каждый номер ровно одному ведру. Вы можете сделать это, добавив следующее ограничение для каждого числа «i»:

x_i1 + x_i2 + ... + x_in = 1

У вас также есть ограничения диапазона для каждого сегмента "j":

100 <= y_1 x_1j + y_2 x_2j + ... + y_m x_mj <= 150

На самом деле вы просто ищете любые осуществимые решения, поэтому вы можете просто установить цель на 0 и рассматривать это как проблему осуществимости.

Пока вы решаете NP-полную задачу, так что это теоретически сложное упражнение, вы можете обнаружить, что современное программное обеспечение для оптимизации может решить задачу для интересующих вас размеров задач.

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

library(lpSolve)
range.assign <- function(weights, n, min.sum, max.sum) {
  m <- length(weights)
  one.mat <- t(sapply(1:m, function(i) c(replicate(n, 1*((1:m) == i)))))
  w.mat <- t(sapply(1:n, function(j) c(rep(0, m*(j-1)), weights, rep(0, m*(n-j)))))
  mod <- lp(objective.in = rep(0, n*m),
            const.mat = rbind(one.mat, w.mat, w.mat),
            const.dir = rep(c("=", ">=", "<="), c(m, n, n)),
            const.rhs = rep(c(1, min.sum, max.sum), c(m, n, n)),
            all.bin=TRUE)
  if (mod$status == 0) {
    apply(matrix(mod$solution, nrow=m), 1, function(x) which(x >= 0.999))
  } else {
    rep(NA, m)
  }
}
range.assign(1:5, 2, 5, 10)
# [1] 1 1 1 1 2
range.assign(1:5, 2, 5, 6)
# [1] NA NA NA NA NA

Я протестировал это с m весами, выбранными случайным образом из [1, 2, ..., 10], допустимым диапазоном для корзины [100, 150] и общим количеством корзин n = ceiling(5.5*m / 125). Я увидел следующее масштабирование во время выполнения:

• m = 100, n = 5: 0,1 секунды
• m = 200, n = 9: 0,6 секунды
• m = 300, n = 14: 2,2 секунды
• m = 400, n = 18: 16,9 секунды

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

1. Использование коммерческих решателей, таких как Gurobi или cplex (оба платные в целом, но бесплатны для академического использования).
2. Ввод матрицы ограничений в разреженном формате.

Похоже на проблему k-разбиения, более известную как проблема с упаковкой в ​​bin. проблема NP-Complete, не будет «эффективного» решения. Однако, если вы посмотрите в Интернете, я уверен, что вы можете найти множество примеров кода, чтобы вы и ваши (*кашель*) "коллеги" могли решить эту проблему.