Справедливый алгоритм распределения товаров

Вот моя проблема:

  • Есть n компаний, распространяющих продукцию.
  • Все продукты должны быть распределены в k дней
  • Распространение продукции компании Ci должно быть последовательным - это значит, что ее можно распространять в дни 2,3,4,5, но не 2,3,6,7
  • количество распределенных продуктов компанией Ci в день j должно быть меньше (или равно) в день j-1 (если таковые были в день j-1)
  • разница между распределенными продуктами между днями i и j не должна превышать 1

Пример:

У нас есть 3 дня для распространения продукции. Продукция компании А: а, а, а, а, а. Продукция компании B: B, B, B. Продукция компании C: C, C

Справедливое распространение:[aab, aabc, abc]

Неверноераспределение:[aabc, aabc, ab], потому что в 1-й день есть 4 продукта, в 3-й день 2 продукта (разница> 1)

Неверноераспределение:[abc, aabc, aab], потому что в 1-й день есть один продукт A, а во 2-й день - 2 продукта A, поэтому распределение продукта A не уменьшается

РЕДАКТИРОВАТЬ, если есть случай, который делает справедливое распространение невозможным, предоставьте его с кратким описанием, я приму ответ

Источник

4 ответа

Решение

Комментарий Гарета Риса к ответу Джны прав - следующий контрпример неразрешим:

  • 3 дня, 7 предметов от компании А и 5 предметов от компании Б

Я проверил это с помощью следующей самой тупой Perl-программы грубой силы (которая занимает не более секунды, несмотря на то, что она очень неэффективна):

my ($na, $nb) = (7, 5);
for (my $a1 = 0; $a1 <= $na; ++$a1) {
    for (my $a2 = 0; $a2 <= $na - $a1; ++$a2) {
        my $a3 = $na - $a1 - $a2;
        for (my $b1 = 0; $b1 <= $nb; ++$b1) {
            for (my $b2 = 0; $b2 <= $nb - $b1; ++$b2) {
                my $b3 = $nb - $b1 - $b2;
                if ($a1 >= $a2 && $a2 >= $a3 || $a1 == 0 && $a2 >= $a3 || $a1 == 0 && $a2 == 0) {
                    if ($b1 >= $b2 && $b2 >= $b3 || $b1 == 0 && $b2 >= $b3 || $b1 == 0 && $b2 == 0) {
                        if (max($a1 + $b1, $a2 + $b2, $a3 + $b3) - min($a1 + $b1, $a2 + $b2, $a3 + $b3) <= 1) {
                            print "Success! ($a1,$a2,$a3), ($b1,$b2,$b3)\n";
                        }
                    }
                }
            }
        }
    }
}

Пожалуйста, посмотрите и убедитесь, что я не совершил глупых ошибок. (Я опустил max() а также min() для краткости - они просто делают то, что вы ожидаете.)

Источник

Так как я думал, что проблема была забавной, я сделал модель для поиска решений, используя MiniZinc. В бэкэнде Gecode показано, что первоначальный пример имеет 20 решений примерно за 1,6 мс.

include "globals.mzn";

%%% Data
% Number of companies
int: n = 3;
% Number of products per company
array[1..n] of int: np = [5, 3, 2];
% Number of days
int: k = 3;

%%% Computed values
% Total number of products
int: totalnp = sum(np);
% Offsets into products array to get single companys products 
% (shifted cumulative sum).
array[1..n] of int: offset = [sum([np[j] | j in 1..i-1]) 
                          | i in 1..n];

%%% Predicates
predicate fair(array[int] of var int: x) =
      let { var int: low,
            var int: high
      } in
        minimum(low, x) /\
        maximum(high, x) /\
        high-low <= 1;
predicate decreasing_except_0(array[int] of var int: x) =
        forall(i in 1..length(x)-1) (
                 (x[i] == 0) \/
                 (x[i] >= x[i+1])
        );
predicate consecutive(array[int] of var int: x) =
        forall(i in 1..length(x)-1) (
             (x[i] == x[i+1]) \/
             (x[i] == x[i+1]-1)
        );

%%% Variables
% Day of production for all products from all companies
array[1..totalnp] of var 1..k: products 
          :: is_output;
% total number of products per day
array[1..k] of var 1..totalnp: productsperday 
        :: is_output;

%%% Constraints 
constraint global_cardinality(products, productsperday);
constraint fair(productsperday);
constraint
    forall(i in 1..n) (
         let { 
             % Products produced by company i
             array[1..np[i]] of var int: pi
                = [products[j] | 
                 j in 1+offset[i]..1+offset[i]+np[i]-1],
             % Products per day by company i
             array[1..k] of var 0..np[i]: ppdi
         } in
           consecutive(pi) /\
           global_cardinality(pi, ppdi) /\
           decreasing_except_0(ppdi)
    );

%%% Find a solution, default search strategy
solve satisfy;

Предикаты decreasing_except_0 а также consecutive оба очень наивны, и имеют большие разложения. Для решения более крупных случаев, вероятно, следует заменить их на более умные варианты (например, с помощью регулярного ограничения).

Источник

Было показано, что пункты 4 и 5 были несовместимы:

  • 4: Для любого дня j, для любой компании A, C(j,A) == 0 или C (j, A)> = C (j + 1, A)
  • 5: Для любых дней я и J, |C(i) - C(j)| <= 1

Таким образом, вам нужно ослабить любое ограничение. Честно говоря, пока я чувствую, почему 4 был введен в действие (чтобы избежать задержки распространения одной компании на неопределенный срок) Я думаю, что можно было бы выразить иначе рассматривать первый и последний день распространения как особые (поскольку в первый день вы обычно берете то, что осталось от предыдущей компании) и в последний день раздаешь то что осталось).

Точка 3 заставляет смежность.

Математически:

Для любой компании A, которая имеет продукцию, существует два дня i и j, такие что:

  • C (i, A)> 0 и C(j,A) > 0
  • для любого дня x такого, что x j, C(x,A) = 0
  • для любого дня x такого, что i

По общему признанию, проблема тогда становится тривиальной, чтобы решить:)

Источник

Я не думаю, что вы всегда можете выполнить ваши требования.

Рассмотрим 4 дня и 6 товаров от поставщика A и 6 товаров от поставщика B.

Источник
Другие вопросы по тегам