分配珠子拼图的算法(2)？

Question

假设您有一个带有 N 个槽的圆(如下所示)。 您的目标是最终在每个插槽中放置指定数量的珠子，并且您有一个大小为 N 的数组，其中包含每个插槽中所需的珠子数量。例如，如果数组是 {1, 5, 3}，那么您最终需要在槽 1 中有 1 个珠子，在槽 2 中有 5 个珠子，在槽 3 中有 3 个珠子。您有无限数量的珠子。

您可以“解锁”X 个插槽。解锁插槽后，您就可以开始将珠子放入该插槽中。您可以移动已经在插槽中的珠子，但您只能顺时针移动。

要解决问题，珠子必须移动的最小距离是多少？

这是一个例子:

N = 6，X = 2。数组:{2, 5, 4, 2, 6, 2}

解锁插槽 2 和 5。将 11 颗珠子放入插槽 2 并移动总距离 8 以到达插槽 2、3 和 4。将 10 颗珠子放入插槽 5 并移动总距离 6 以到达插槽5、6 和 1。8 + 6 = 14，所以答案是 14。

Answer 1

这个问题有一些需要注意的地方:

• 将珠子移动到(或超出)另一个未锁定的插槽没有任何好处，因为如果这些珠子从另一个未锁定的插槽开始移动的次数会更少；
• 因此，一旦选择了要解锁的插槽，就可以确定要放入其中的珠子数量以及移动次数；
• 如果已经为一组特定的未锁定插槽计算了成本(移动次数)，则可以轻松导出相邻配置的成本(其中先前解锁的插槽保持锁定状态，但下一个插槽已解锁)，无需从头开始计算；
• 在最佳解决方案中，必须接收最多 bean 的插槽总是未锁定是不正确的；
• 如果一个插槽选择保持可变，则成本将在选择下一个插槽的方向上增加或减少，这是不正确的；它可以上升和下降，再次上升和下降。

此处建议的算法将遍历所有 combinations可能的插槽选择并选择具有最低移动的组合。因此，时间复杂度为 O(n!/[(n-x)!x!])。

我认为应该有一个更高效的算法，它不需要访问所有组合，但我没有找到允许这样做的任何数学模式。

这是 JavaScript 代码段中的算法:

function optimalCollectors(beadCounts, collectorCount) {
    // Initialisation
    var n = beadCounts.length;
    if (n < collectorCount) return {error: "not enough slots"};
    var beads = beadCounts.reduce(function (beads, beadCount) {
        return beads + beadCount;
    });
    var cost = beadCounts.reduce(function (cost, beadCount, idx) {
        return cost + beadCount * (idx+1);
    });
    var solution = {
        cost: cost, // too large, to make sure it gets improved
        slots: [] // numbers of the slots chosen for the solution
    };
    var collectorSlots = Array(collectorCount);

    function findNextCollector(collectorNo, startSlot, cost, beads) {
        var addBeads = 0;
        for (var slot=startSlot; slot<=n-collectorCount+collectorNo; slot++) {
            collectorSlots[collectorNo] = slot;
            // progressively calculate total cost, and number of beads
            // "in front" of the currently tried slot.
            cost -= beads;
            beads += addBeads - beadCounts[slot];
            if (collectorNo == collectorCount - 1) { // all slots chosen
                if (cost < solution.cost) { // found a current best
                    solution.cost = cost;
                    // copy currently selected slot numbers:
                    solution.slots = collectorSlots.slice(0);
                }
            } else {
                findNextCollector(collectorNo+1, slot+1, cost, beads);
            }
            if (collectorNo) {
                cost += beadCounts[slot] * (slot + 1 - startSlot);
            } else {
                cost += beadCounts[slot] * (n - 1);
                addBeads = beadCounts[slot];
            }
        }
    }
    
    findNextCollector(0, 0, cost, beads);
    return solution;
}

function randomInput(n) {
    // The random values are in the range 0..n-1. This is just 
    // a convenient choice, in reality there has not to be a limit.
    return Array.from({length: n}, x => Math.floor(Math.random() * n));
}

// Link with I/O
var beads = document.getElementById('beads');
var collectors = document.getElementById('collectors');
var randomize = document.getElementById('randomize');
var calculate = document.getElementById('calculate');
var output = document.getElementById('output');

// Capture events
randomize.onclick = function() {
    var n = 5 + Math.floor(Math.random() * 7);
    beads.value = randomInput(n).join(',');
    collectors.value = 2 + Math.floor(Math.random() * (n/2-2));
    calculate.onclick();
};

calculate.onclick = function() {
    var beadCounts = beads.value.split(',').map(Number);
    var collectorCount = Number(collectors.value);
    var solution = optimalCollectors(beadCounts, collectorCount);
    if (solution.error) {
        output.textContent = 'Error: ' + solution.error;
        return;
    }
    output.textContent = 
        '\nInput: ' + JSON.stringify(beadCounts) +
        '\nNumber of moves: ' + solution.cost +
        '\nChosen slots (0-based): ' + JSON.stringify(solution.slots);
};

Comma-separated list of number of beads per slot:<br/>
<input id="beads" size="30" value="2, 5, 4, 2, 6, 2">
<button id="randomize">Randomize</button><br/>
Number of bead-collecting slots:<br/>
<input id="collectors" size="3" value="2"></br>
<button id="calculate">Find collector slots minimising cost</button></br>
<pre id="output"></pre>