嗨,我正在寻找一种算法,将一组正数分成k个部分,以便每个部分具有(大约)相同的总和...假设我们有
1,2,3,4,5,6,7,8,9,k = 3,则应该将算法分区如下1,2,3,4,5 | 6,7 | 8,9 元素的顺序不能改变...找到贪心算法很容易,但我正在寻找一种回溯版本,它始终返回最优解...
有任何提示吗?
嗨,我正在寻找一种算法,将一组正数分成k个部分,以便每个部分具有(大约)相同的总和...假设我们有
1,2,3,4,5,6,7,8,9,k = 3,则应该将算法分区如下1,2,3,4,5 | 6,7 | 8,9 元素的顺序不能改变...找到贪心算法很容易,但我正在寻找一种回溯版本,它始终返回最优解...
有任何提示吗?
“最优解”是什么意思?我认为你的意思是指将每个分区距离最佳分区的总和最小化的解。最佳分区应该是其元素之和等于总和除以分区数的分区。
如果您不关心效率,那么可能这种粗略的方法已经足够好了。我尚未对算法进行测试以检查其正确性,请小心使用。
void FindPartitions(int[] numbers, int i, IList<int>[] partitions, int currentPartition, IList<int>[] bestSolution, ref int minDistance)
{
if (i == numbers.Length)
{
int sum = numbers.Sum();
int avg = sum / partitions.Length;
int currentDistance = 0;
foreach (var partition in partitions)
currentDistance += Math.Abs(partition.Sum() - avg);
if (currentDistance < minDistance)
{
minDistance = currentDistance;
for (int j = 0; j < partitions.Length; j++)
bestSolution[j] = new List<int>(partitions[j]);
}
}
else
{
partitions[currentPartition].Add(numbers[i]);
FindPartitions(numbers, i + 1, partitions, currentPartition, bestSolution, ref minDistance);
partitions[currentPartition].RemoveAt(partitions[currentPartition].Count - 1);
if (currentPartition < partitions.Length - 1)
FindPartitions(numbers, i, partitions, currentPartition + 1, bestSolution, ref minDistance);
}
}
int start[K];
void register() {
/* calculate the error between minimum and maximum value partitions */
/* partition boundaries are start[0], start[1], start[2], ... */
/* if lower error than previously stored, remember the best solution */
}
void rec(int s, int k) {
if (k == K) register();
for (int i = s; i < N; i++) {
start[k] = i;
rec(i + 1, k + 1);
}
}
/* entry */
start[0] = 0;
rec(1, 1);
/* then output the best solution found at register() */
注意:这是一个O(nK)算法。它是次指数级的,因为它与一般的NP完全分割问题不同,在这里你要寻找线性数组的连续段,而不是给定总集合的任意子集。
这是一个JavaScript中的递归算法。该函数返回每个工人将被分配的总数。假设输入数组bookLoads是一组正数,您希望尽可能公平地将其分成k部分(比如在k个工人之间)
这是一个可用的fiddle链接: https://jsfiddle.net/missyalyssi/jhtk8vnc/3/
function fairWork(bookLoads, numWorkers = 0) {
// recursive version
// utilities
var bestDifference = Infinity;
var bestPartition = {};
var initLoads = {};
var workers = Array.from({length: numWorkers}, (val, idx) => {
initLoads[idx] = 0;
return idx;
});
var bookTotal = bookLoads.reduce((acc, curr) => {return acc + curr}, 0);
var average = bookTotal / bookLoads.length;
// recursive function
function partition(books = bookLoads, workers, loads={}) {
// if only one worker give them all the books
if (workers.length == 1 && books.length > 0) {
var onlyWorker = workers[0];
loads[onlyWorker] += books.reduce((acum, curr, idx, arr) => {
return acum + curr;
},0);
books = [];
}
// base case
if (books.length == 0) {
var keys = Object.keys(loads);
var total = 0;
for (let key = 0; key < keys.length; key++) {
// square so that difference shows
total += Math.pow(Math.abs(average - loads[keys[key]]), 2);
}
if (total < bestDifference) {
bestDifference = total;
bestPartition= loads;
}
return bestPartition;
}
var currBookLoad = books[0];
// add book to curr worker 1
var newWorker1Loads = Object.assign({}, loads);
var worker1 = workers[0];
newWorker1Loads[worker1] = newWorker1Loads[worker1] + currBookLoad || currBookLoad;
partition(books.slice(1), workers, newWorker1Loads)
// give to next worker
var newNextWorkerLoads = Object.assign({}, loads);
var worker2 = workers[1];
newNextWorkerLoads[worker2] = newNextWorkerLoads[worker2] + currBookLoad || currBookLoad;
partition(books.slice(1), workers.slice(1), newNextWorkerLoads)
return bestPartition;
}
// function call
return partition(bookLoads, workers, initLoads)
}
fairWork([3,1,2,3], 3)
//Result will be: Object {0: 3, 1: 3, 2: 3}
fairWork([1,2,3,4,5,6,7,8,9], 3)
//Result will be: Object {0: 15, 1: 13, 2: 17}