Делить ресурсы K справедливо на N человек

Question

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

• Они все принимают непрерывный набор точек на круге. То есть они не может владеть сегментированными сокровищами.
• Все сокровища должны быть выделены
• Каждое сокровище должно принадлежать только одному человеку.

Например, если есть 4 сокровища и 2 человека, как показано на рисунке, тогда оптимальный способ деления будет

(6, 10) и (11, 3) => с разницей 2.

1 <= n <= 25 </p>

1 <= k <= 50 </p>

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

Я был бы рад, если бы кто-нибудь пролил немного света.

Answer 1

Учтите, что для каждого k мы можем связать сумму, растущую с A[i] влево (sum A[i-j..i]), со всеми доступными интервалами, записанными для f(k-1, i-j-1), и обновить их: для каждого интервала (low, high), если сумма больше high, то new_interval = (low, sum), а если сумма меньше low, то new_interval = (sum, high); в противном случае интервал остается неизменным. Например,

i:  0 1 2 3 4 5
A: [5 1 1 1 3 2]

k = 3
i = 3, j = 0
The ordered intervals available for f(3-1, 3-0-1) = f(2,2) are:
  (2,5), (1,6) // These were the sums, (A[1..2], A[0]) and (A[2], A[0..1])
Sum = A[3..3-0] = 1
Update intervals: (2,5) -> (1,5)
                  (1,6) -> (1,6) no change

Теперь мы можем сделать эту итерацию намного более эффективной, распознавая и сокращая интервалы во время предыдущего раунда k.

Часы

A: [5 1 1 1 3 2]

K = 1:

  N = 0..5; Intervals: (5,5), (6,6), (7,7), (8,8), (11,11), (13,13)

K = 2:

  N = 0: Intervals: N/A

  N = 1: Intervals: (1,5)

  N = 2: (1,6), (2,5)

    Prune: remove (1,6) since any sum <= 1 would be better paired with (2,5)
           and any sum >= 6 would be better paired with (2,5)

  N = 3: (1,7), (2,6), (3,5)

    Prune: remove (2,6) and (1,7)

  N = 4: (3,8), (4,7), (5,6), (5,6)

    Prune: remove (3,8) and (4,7)

  N = 5: (2,11), (5,8), (6,7)

    Prune: remove (2,11) and (5,8)

Для k = 2 у нас осталась следующая сокращенная запись:

{
  k: 2,
  n: {
    1: (1,5),
    2: (2,5),
    3: (3,5),
    4: (5,6),
    5: (6,7)
  }
}

Мы сократили итерацию k = 3 из списка n choose 2 возможных разбиений до n соответствующих разбиений!

Общий алгоритм, применяемый к k = 3:

for k' = 1 to k
  for sum A[i-j..i], for i <- [k'-1..n], j <- [0..i-k'+1]:
    for interval in record[k'-1][i-j-1]: // records are for [k'][n']
      update interval
  prune intervals in k'

k' = 3
  i = 2
    sum = 1, record[2][1] = (1,5) -> no change

  i = 3
    // sums are accumulating right to left starting from A[i]
    sum = 1, record[2][2] = (2,5) -> (1,5)
    sum = 2, record[2][1] = (1,5) -> no change

  i = 4
    sum = 3, record[2][3] = (3,5) -> no change
    sum = 4, record[2][2] = (2,5) -> no change
    sum = 5, record[2][1] = (1,5) -> no change

  i = 5
    sum = 2, record[2][4] = (5,6) -> (2,6)
    sum = 5, record[2][3] = (3,5) -> no change
    sum = 6, record[2][2] = (2,5) -> (2,6)
    sum = 7, record[2][1] = (1,5) -> (1,7)

Ответ 5 в паре с record[2][3] = (3,5), что дает обновленный интервал (3,5). Я оставлю логику обрезки для читателя. Если мы хотим продолжить, вот сокращенный список для k = 3

{
  k: 3
  n: {
    2: (1,5), 
    3: (1,5),
    4: (3,5),
    5: (3,5)
  }
}

Answer 2

Вы можете сделать перебор для O (k ^ n) или dp для O (k ^ {2} * MAXSUM ^ {k - 1}).

dp [i] [val1] [val2] ... [val k -1] можно ли распределить первые k элементов, поэтому сначала есть val1, второй - val2 и так далее. Есть k * MAXSUM (k - 1) состояний, и вам нужно O (k), чтобы сделать шаг, вы просто выбираете, кто получает i-й предмет.

Я не думаю, что это можно решить быстрее.

Answer 3

Нет стандартного типа алгоритма (жадный, разделяй и властвуй и т. Д.) Для этой проблемы.
Вам нужно будет проверить каждую комбинацию (resource, people) и выбрать ответ. Как только вы решили проблему с помощью рекурсии, вы можете бросить DP, чтобы оптимизировать решение.

Суть решения:

Recuse through all the treasures
    If you current treasure is not the last,
        set minimum difference to Infinity
            for each user
                assign the current treasure to the current user 
                ans = recurse further by going to the next treasure
                update minimumDifference if necessary
    else 
       Find and max amount of treasure assigned and minimum amount of treasure assigned
       and return the difference

Вот javascript версия ответа. Я прокомментировал это, чтобы попытаться объяснить логику также:

// value of the treasure
const K = [6, 3, 11, 10];
// number of users
const N = 2;

// Array which track amount of treasure with each user
const U = new Array(N).fill(0);

// 2D array to save whole solution
const bitset = [...new Array(N)].map(() => [...new Array(K.length)]);

const solve = index => {
    /**
     * The base case:
     * We are out of treasure.
     * So far, the assigned treasures will be in U array
     */
    if (index >= K.length) {
        /**
         * Take the maximum and minimum and return the difference along with the bitset
         */
        const max = Math.max(...U);
        const min = Math.min(...U);
        const answer = { min: max - min, set: bitset };
        return answer;
    }

    /**
     * We have treasures to check
     */
    let answer = { min: Infinity, set: undefined };
    for (let i = 0; i < N; i++) {
        // Let ith user take the treasure
        U[i] += K[index];
        bitset[i][index] = 1;
        /**
         * Let us recuse and see what will be the answer if ith user has treasure at `index`
         * Note that ith user might also have other treasures for indices > `index`
         */
        const nextAnswer = solve(index + 1);

        /**
         * Did we do better?
         * Was the difference bw the distribution of treasure reduced?
         * If so, let us update the current answer
         * If not, we can assign treasure at `index` to next user (i + 1) and see if we did any better or not
         */
        if (nextAnswer.min <= answer.min) {
            answer = JSON.parse(JSON.stringify(nextAnswer));
        }

        /**
         * Had we done any better,the changes might already be recorded in the answer.
         * Because we are going to try and assign this treasure to the next user,
         * Let us remove it from the current user before iterating further
         */
        U[i] -= K[index];
        bitset[i][index] = 0;
    }
    return answer;
};

const ans = solve(0);
console.log("Difference: ", ans.min);
console.log("Treasure: [", K.join(", "), "]");
console.log();
ans.set.forEach((x, i) => console.log("User: ", i + 1, " [", x.join(", "), "]"));

Каждая проблема с индексом i создает ровно N копий само по себе и у нас всего K показателей, сложность по времени проблемы решить это O(K^N)

Мы можем определенно сделать лучше, бросая памятку.

А вот и сложная часть:

Если у нас есть распределение сокровищ для одного пользователя, минимум Разница в распределении сокровищ среди пользователей будет то же самое.

В нашем случае bitset[i] представляет дистрибутив для ith пользователя. Таким образом, мы можем запомнить результаты для bitset пользователя.

Тот, который вы понимаете, кодирование это просто:

// value of the treasure
const K = [6, 3, 11, 10, 1];
// number of users
const N = 2;

// Array which track amount of treasure with each user
const U = new Array(N).fill(0);

// 2D array to save whole solution
const bitset = [...new Array(N)].map(() => [...new Array(K.length).fill(0)]);

const cache = {};

const solve = (index, userIndex) => {
    /**
     * Do we have cached answer?
     */
    if (cache[bitset[userIndex]]) {
        return cache[bitset[userIndex]];
    }

    /**
     * The base case:
     * We are out of treasure.
     * So far, the assigned treasures will be in U array
     */
    if (index >= K.length) {
        /**
         * Take the maximum and minimum and return the difference along with the bitset
         */
        const max = Math.max(...U);
        const min = Math.min(...U);
        const answer = { min: max - min, set: bitset };
        // cache the answer
        cache[bitset[userIndex]] = answer;
        return answer;
    }

    /**
     * We have treasures to check
     */
    let answer = { min: Infinity, set: undefined };
    // Help us track the index of the user with optimal answer
    let minIndex = undefined;
    for (let i = 0; i < N; i++) {
        // Let ith user take the treasure
        U[i] += K[index];
        bitset[i][index] = 1;
        /**
         * Let us recuse and see what will be the answer if ith user has treasure at `index`
         * Note that ith user might also have other treasures for indices > `index`
         */
        const nextAnswer = solve(index + 1, i);

        /**
         * Did we do better?
         * Was the difference bw the distribution of treasure reduced?
         * If so, let us update the current answer
         * If not, we can assign treasure at `index` to next user (i + 1) and see if we did any better or not
         */
        if (nextAnswer.min <= answer.min) {
            answer = JSON.parse(JSON.stringify(nextAnswer));
            minIndex = i;
        }

        /**
         * Had we done any better,the changes might already be recorded in the answer.
         * Because we are going to try and assign this treasure to the next user,
         * Let us remove it from the current user before iterating further
         */
        U[i] -= K[index];
        bitset[i][index] = 0;
    }
    cache[answer.set[minIndex]] = answer;
    return answer;
};

const ans = solve(0);

console.log("Difference: ", ans.min);
console.log("Treasure: [", K.join(", "), "]");
console.log();
ans.set.forEach((x, i) => console.log("User: ", i + 1, " [", x.join(", "), "]"));

// console.log("Cache:\n", cache);

Мы определенно можем улучшить используемое пространство, не кэшируя весь набор битов. Удаление набора битов из cahce тривиально.

Answer 4

Так, скажем, мы фиксируем x, y как минимум, максимально допустимый для сокровища. Мне нужно выяснить, сможем ли мы найти решение в этих ограничениях.

Для этого мне нужно пройти по кругу и создать ровно N сегментов с суммами между x и y. Это я могу решить с помощью динамического программирования, a [i] [j] [l] = 1, если я могу разбить элементы между i и j на l, чьи суммы находятся между x и y (см. Выше). Чтобы вычислить его, мы можем оценить a [i] [j] [l] = is_there_a_q_such_that (a [i] [q - 1] [l-1] == 1 и сумму (q -> j) между x и y). Чтобы справиться с кругом, ищите n-1 сегментов, которые покрывают достаточно элементов, а оставшееся различие остается между x и y.

Таким образом, наивным решением является O (total_sum ^ 2) для выбора X и Y плюс O (K ^ 3) для итерации по i, j, l и другому O (K), чтобы найти aq и еще одно O (K), чтобы получить сумма. Это всего O (total_sum ^ 2 * K ^ 5), что, вероятно, слишком медленно.

Так что нам нужно много вычислять. Итак, давайте предварительно вычислим массив частичных сумм sums [w] = sum (элементы между pos 0 и pos w). Таким образом, чтобы получить сумму между q и j, вам нужно только вычислить суммы [j] - суммы [q-1]. Это заботится о O (K).

Для вычисления a [i] [j] [l]. Так как сокровища всегда положительны, если частичная сумма слишком мала, нам нужно увеличить интервал, если сумма слишком велика, нам нужно уменьшить интервал. Так как мы зафиксировали сторону интервала (в точке j), мы можем только переместить q. Мы можем использовать бинарный поиск, чтобы найти замыкания t и самые дальние q, которые позволяют нам находиться между x и y. Давайте назовем их low_q (ближайший к j, самая низкая сумма) и high_q (далеко от j, самая большая сумма). Если low_q У нас все еще есть total_sum ^ 2 впереди. Допустим, мы исправим X. Если для данного y у нас есть решение, вы можете найти также меньший y, у которого все еще есть решение. Если вы не можете найти решение для данного y, то вы не сможете найти решение для любого меньшего значения. Теперь мы можем выполнить бинарный поиск по y.

Так что теперь это O (total_sum * log (total_sum) * K ^ 3 * logK).

Другая оптимизация состояла бы в том, чтобы не повышать i, если сумма (0-> i- 1)> x. Возможно, вы не захотите проверять значения x> total_sum / K, поскольку это идеальное минимальное значение. Это должно компенсировать одну из сложностей.

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