将K资源公平分配给N个人

Question

圆上有代表宝藏位置的K点。N的人们想要分享宝藏。你想要把宝藏公平地分配给所有的人，这样，拥有最大价值的人和拥有最小价值的人之间的差别就越小越好。

• 他们都在圆圈上取了一组连续的点。也就是说，他们不能拥有分割的宝藏。
• 所有的财宝都必须分配。
• 每一件珍宝只应属于一个人。

例如，如图中所示，如果有4个宝藏和2个人，那么最佳的划分方法是

​

​

(6，10)和(11，3) =>，差异为2。

1 <= n <= 25 1 <= k <= 50

我该如何解决这个问题？我计划计算所有点数的平均值，并不断增加资源，直到它们小于每个人的平均值为止。但是，尽管它是显而易见的，但它并不能在所有情况下都奏效。

如果有人放点光我会很高兴的。

Answer 1

所以假设我们把x，y修正为最小允许的宝藏。我需要弄清楚我们能否在这些约束条件下找到一个解决方案。

为此，我需要遍历圆圈，在x和y之间创建精确的N段，这可以通过动态规划( ail =1)来求解，如果我能将i和j之间的元素分解为l，其和在x和y之间(见上文)。为了计算它，我们可以计算ail =is_there_a_q_such_that(ai-1 == 1和和(q -> j)在x和y之间)。要处理圆圈，请查找包含足够多元素的n-1段，其余的差异仍保留在x和y之间。

因此，朴素解是: O(total_sum^2)选择X和Y+ O(K^3)迭代i，j，l和另一个O(K)，求Q，另一个O(K)求和。这总共是O(total_sum^2 * K^5)，它可能太慢了。

所以我们需要计算大量的和。因此，让我们预先计算一个部分和数组和w=sum(pos0和pos之间的元素)。因此，要得到q与j之间的和，只需计算和j-和-1。这就照顾到了O(K)。

来计算电子邮件。由于财富总是正数，如果部分和太小，我们需要增长间隔，如果和太高，我们需要缩小间隔。如果我们固定了区间( j)的一个边，我们只能移动q，我们可以用二进制搜索来找到使我们介于x和y之间的闭包t和最远的q，让我们称它们为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)。

如果和(0->i-1)> x，则其他优化将不提高i。您可能不想检查x> total_sum/K的值，因为这是理想的最小值。这应该抵消掉其中一个K的复杂性。

也许还有其他的事情你可以做，但我认为这将足以满足您的限制。

Answer 2

您可以对O(k^n)执行蛮力操作，对于O(k^{2}*MAXSUM^{k-1})可以执行dp。

dpival2...val k -1是可以分发第一个k项的，所以首先有val1，第二个- val2等等.有k个 * MAXSUM(k - 1)状态，您需要O(k)来执行步骤，您只需选择谁拿这个项。

我认为不可能更快地解决这个问题。

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中删除位集是非常简单的。