Застрял в интервью Вопрос ... Разбиение массива

Question

Я обнаружил в Интернете следующую проблему и хотел бы узнать, как мне ее решить:

Проблема: Целочисленный раздел без перестановки

Ввод: Расположение S неотрицательных чисел {s ₁ ,.,,, s _n } и целое число k.

Вывод: Разделение S на k или менее диапазонов, чтобы минимизировать максимум сумм всех k или менее диапазонов, без переупорядочения любого числа. *

Пожалуйста, помогите, кажется интересным вопросом ... На самом деле я провожу довольно много времени, но не смог найти никакого решения ..

Answer 1

Давайте попробуем решить проблему с помощью динамического программирования.

Примечание: если k> n , мы можем использовать только n интервалы.

Давайте рассмотрим d [i] [j] - решение проблемы, когда S = { s ₁ , ..., с _i } и k = j .Таким образом, легко увидеть, что:

1. d [0] [j] = 0 для каждого j от 1 до k
2. d [i] [1] = сумма (с ₁ ... s _i ) длякаждый i от 1 до n
3. d [i] [j] = мин _{для t = 1 доi} (max (d [i - t] [j - 1], сумма (s _{i - t + 1} ... s _i )) для i = 1к n и j = 2 к k

Теперь давайте посмотрим, почему это работает:

1. Когда в последовательности нет элементовясно, что может существовать только один интервал (пустой), а сумма его элементов равна 0. Поэтому d [0] [j] = 0 для всех j из 1 до k .
2. Когда может быть только один интервал, ясно, что решение является суммой всех элементов последовательности. Так что d [i] [1] = сумма (с ₁ ... с _i ) .
3. Теперь давайте рассмотрим, есть i элементы впоследовательность и количество интервалов j , мы можем предположить, что последний интервал (s _{i - t + 1} ... s _i ) где t - положительное целое число, не превышающее i , поэтому в этом случае решение будет max (d [i - t] [j - 1], сумма (s _{i - t)+ 1} ... s _i ) , но, поскольку мы хотим, чтобы решение было минимальным, мы должны выбрать t , чтобы минимизировать его, поэтому мы получим min _{для t = 1 до i} (max (d [i - t] [j - 1], сумма (s _{i - t + 1} ... s _)i )) .

Пример:

S = (5,4,1,12), k =2

d [0] [1] = 0, d [0] [2] = 0

d [1] [1] = 5, d [1] [2] = 5

d [2] [1] = 9, d [2] [2] = 5

d [3] [1] = 10, d [3] [2] = 5

d [4] [1] = 22, d [4] [2] = 12

Код:

#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;

int main ()
{
    int n;
    const int INF = 2 * 1000 * 1000 * 1000;
    cin >> n;
    vector<int> s(n + 1);
    for(int i = 1; i <= n; ++i)
        cin >> s[i];
    vector<int> first_sum(n + 1, 0);
    for(int i = 1; i <= n; ++i)
        first_sum[i] = first_sum[i - 1] + s[i];
    int k;
    cin >> k;
    vector<vector<int> > d(n + 1);
    for(int i = 0; i <= n; ++i)
        d[i].resize(k + 1);
    //point 1
    for(int j = 0; j <= k; ++j)
        d[0][j] = 0;
    //point 2
    for(int i = 1; i <= n; ++i)
        d[i][1] = d[i - 1][1] + s[i]; //sum of integers from s[1] to s[i]
    //point 3
    for(int i = 1; i <= n; ++i)
        for(int j = 2; j <= k; ++j)
        {
            d[i][j] = INF;
            for(int t = 1; t <= i; ++t)
                d[i][j] = min(d[i][j], max(d[i - t][j - 1], first_sum[i] - first_sum[i - t]));
        }


    cout << d[n][k] << endl;
    return 0;
}

Answer 2

Эта проблема дословно взята из книги Стивена Скиены " Руководство по разработке алгоритма ".Вы можете прочитать подробное обсуждение и его решение на Google Книги .А еще лучше купить книгу .