Как упаковать несколько рюкзаков, которые были на максимальной вместимости, их вещи были сброшены в кучу, перемешаны, и некоторые предметы были удалены? - PullRequest
Новая
       41

Как упаковать несколько рюкзаков, которые были на максимальной вместимости, их вещи были сброшены в кучу, перемешаны, и некоторые предметы были удалены?

0 голосов
/ 18 февраля 2019

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

Есть n рюкзака, каждый из которых заполнен предметами до его индивидуальной максимальной грузоподъемности C[j], где 0 <= j < n.

Рюкзаки опорожняются на стопку, всего m предметов, каждый с весомW[i], где 0 <= i < m.Элементы в стопке перемешиваются, и k элементы удаляются из стопки, где 0 <= k <= m.

n, m, C[j] и W[i] - целые числа, большие нуля;i, j и k являются неотрицательными целыми числами.

Это состояние является начальным входом для алгоритма упаковки.

Как переупаковать все остальные m - k предметов, чтобы не превышать индивидуальную вместимость каждого рюкзака C[j]?

  • Упаковщик не знает, как ранее были упакованы рюкзаки
  • Рюкзаки былиранее упаковано, поэтому существует правильное решение
  • Количество используемых ранцев не нуждается в оптимизации, также могут быть пустые и / или недостаточно упакованные ранцы
  • Предметы не могут быть разбиты на более легкие части, даже если полученные веса также целые числа
  • При необходимости предметы и рюкзаки можно сортировать
  • Моя самая большая проблема - правильность, а время -более важно, что использование памяти
  • Из предоставленных мной примеров входных данных, как правило, m <= 10 и k ~= 7, но бывают случаи, когда m = 20 или k = 0 или k = m

Iне знаю, гарантируется ли first-fit или упаковка в полный бин алгоритмы гарантированно дадут правильный результат, когда k приближается к нулю, например: если алгоритм упаковывает столько маленькихПредметы, как можно больше, в большом рюкзаке, но затем нужно упаковать большой предмет, и единственный большой рюкзак уже заполнен.

Вот простой пример в Javascript того, чего я хочу достичь: 

let knapsacks = [
  { capacity: 13 },
  { capacity: 9 },
  { capacity: 60 },
  { capacity: 81 }
];

let items = [ 52, 81, 13 ];

// all items packed
let aSolution = [
  {
    capacity: 13,
    items: [ 13 ]
  },
  { capacity: 9 },
  {
    capacity: 65,
    items: [ 52 ]
  },
  {
    capacity: 81,
    items: [ 81 ]
  }
];

// item 81 not packed
let notASolution = [
  { capacity: 13 },
  { capacity: 9 },
  { capacity: 65 },
  {
    capacity: 81,
    items: [ 52, 13 ]
  }
];

1 Ответ

0 голосов
/ 18 февраля 2019

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

...