Алгоритм честного распределения товаров

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

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

Пример:

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

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

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

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

EDIT если есть случай, который делает невозможным честное распространение, дайте краткое описание, я приму ответ

5
задан dfens 9 November 2010 в 12:12
поделиться