Как разбить массив на N наименьших подмножеств суммы?

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

Например, массив состоит из 11 элементов, и мне нужно 6 подмножеств.

{2,1,1,3,4,4,3,2,1,2,3}

Подмножества: {2,1,1,3}, {4}, {4,3}, {3,2}, {1,2}, {3} Минимальная сумма = 7.

альтернативный ответ: {2,1,1} {3,4} {4} {3,2} {1,2} {3} Минимальная сумма = 7.

Примечание: порядок, в котором номера отображаются в исходном наборе, должен поддерживаться при разделении.

источник

2016-05-23 Arijit Pramanick

Я не понимаю, что вы подразумеваете под минимальной суммой. В этой первой строке есть сумма с суммой 3. – Carlos

Разделение массива на N подмножеств, так что сумма каждого подмножества меньше или равна минимальной сумме, возможной из каждого подмножества. –

Попробуйте сделать 6 разделов, где сумма каждого раздела будет меньше 7. –

Один из возможных подходов - двоичный поиск ответа.

Нам нужна процедура, которая проверяет, можно ли разбить набор, используя только суммы, равные или ниже параметра, S. Назовем эту процедуру onlySumsBelow(S).

Мы можем использовать жадные решения для реализации onlySumsBelow(S). Всегда добавляйте как можно больше элементов в каждом подмножестве и останавливайтесь перед достижением суммы, большей, чем S (я предполагаю, что у нас нет отрицательных элементов, что может усложнить обсуждение). Если мы не сможем дойти до конца последовательности, используя допустимое число подмножеств, то сумма недействительна (она слишком мала).

function onlySumsBelow(S) { 
    partitionsUsed = 1; 
    currentSum = 0; 

    for each value in sequence { 
     if (value > S) return false; 

     if (currentSum + value > S) { 
      // start a new partition 
      currentSum = value; 
      partitionsUsed++; 
     } else { 
      currentSum += value; 
     } 
    } 

    return partitionsUsed <= N; 
}

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

Если эффективность не является проблемой, вместо бинарного поиска вы можете просто попробовать несколько ответов кандидатов один за другим, начиная с достаточно малого значения, , например. сумма всех чисел, деленная на N, а затем увеличивается на единицу до достижения тонкого решения.

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

источник

2016-05-23 14:23:05 qwertyman

Как я могу поддерживать количество разделов при добавлении чисел только через процедуруSumsBelow (S)? –

Я добавил несколько псевдокодов для процедуры onlySumsBelow (S).Также упоминалось, что если эффективность не вызывает беспокойства, вы можете избежать двоичного поиска и использовать линейный поиск. – qwertyman

Как разбить массив на N наименьших подмножеств суммы?

ответ

Смежные вопросы