안녕하세요, 각 부분이 (대략) 같은 합계를 갖도록 양수 배열을 k- 파트로 나누는 알고리즘을 찾으려면 도움이 필요합니다. 우리가 가지고 있다고 가정 해 봅시다.분할 문제를 푸는 회귀 - 역 추적 알고리즘
1,2,3,4,5,6,7,8,9 k k = 3 알고리즘은 이것을 1,2,3,4,5 | 6과 같이 파티션해야합니다. 7 | 8,9 요소의 순서는 바꿀 수 없습니다 ... 욕심 많은 알고리즘을 찾는 것은 쉽지만 항상 최적의 솔루션을 반환하는 역 추적 버전을 찾고 있습니다 ...
Annyone은 어떤 힌트가 있습니까?
다음은 목록과 같은 동적 데이터 구조를 사용하지 않는 솔루션입니다. 그것들은 완전히 불필요하며 실제로 알고리즘을 필요한 것보다 훨씬 느리게 만듭니다.
여기서 K는 파티션 수, N은 배열의 요소 수입니다.
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 (N K) 알고리즘이다. 이것은 이 아니기 때문에 sub-exponential입니다.은 일반적인 NP 완성 분할 문제와 동일합니다. 주어진 총합 집합의 임의의 부분 집합 대신 선형 배열의 연속 세그먼트를 찾고 있습니다.
최적의 솔루션이란 무엇을 의미합니까? 나는 당신이 최적의 파티션으로 각 파티션 거리의 합을 최소화하는 것을 의미한다고 생각합니다. 최적의 파티션은 요소 합계가 전체 합계를 파티션 수로 나눈 것과 같은 파티션입니다.
효율성에 대해 신경 쓰지 않는다면이 거친 접근 방식으로 충분할 것입니다. 나는 정확성을 검사하는 알고리즘을 테스트하지 않았으니주의해야한다.
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);
}
}
다음은 자바 스크립트의 재귀 알고리즘입니다. 이 함수는 각 작업자가 할당 될 합계를 반환합니다. 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}