Разделение массива на оптимальное число равных суммарных подвыражений

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

Пример: вес = [1000 500 500] затраты = [150,75,75]

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

Пример: вес = [1000, 500, 500] затраты = [200, 100, 100]

Теперь стоимость всех продуктов составила более 300 долларов США, поэтому мы должны разделить их на пакеты с равными весами, и каждый из них не должен стоить более 300 долларов.

Мы можем разделить их на две упаковки, каждая из которых содержит 1000 грамм, а другая - 1000 грамм (500 + 500), а стоимость не должна превышать 300 долларов.

Я не ищу код или что-то в этом роде. Мне просто нужен намек или алгоритм о том, как действовать в деле деления нескольких пакетов.

1 ответ

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

Но я бы попытался здесь:

let W = total weight of all packages
let N = total number of packages
for k = 1, 2, 3, ..., N
 find all subsets of packages with weight W/k and cost less than $300
 if there an exact cover: stop with solution.

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

licensed under cc by-sa 3.0 with attribution.