数値をバランス良く分ける方法

Question

要素がn個の数列を、m個のグループに分けます。
この時、各グループの数の合計の差ができるだけ小さくなるようにしたいです。
各グループに振り分ける要素の個数はばらつきがあっても構いません。
配列は降順にソート済みとします。

下記のデータの例では、「18, 18, 19」にしたいです。とりあえず単純に、配列の先頭から順に常に合計値が一番小さいグループに加算するというロジックを書きました。これでもまぁまぁ動くのですが、データにより期待より差が大きくなってしまうことがあります。

ですので、もう少しいいロジックにしたいです。動くコードを書いていただけたら嬉しいですが、そうでなくともこういう考え方があるとか、方針のアドバイス等でも嬉しいです。よろしくお願いします。

var data = [6, 6, 6, 6, 5, 5, 4, 3, 3, 3, 2, 2, 2, 2];
var num = 3;

/*
得たい結果の例1 = [
	[6, 6, 3, 3], // 18
	[6, 5, 4, 3], // 18
	[6, 5, 2, 2, 2, 2] // 19
];
得たい結果の例2 = [
	[6, 5, 3, 3, 2], // 19
	[6, 6, 2, 2, 2], // 18
	[6, 5, 4, 3], // 18
];

下記コードの実行結果 = [
	[6, 6, 3, 2, 2], // 19
	[6, 5, 4, 2, 2], // 19
	[6, 5, 3, 3] // 17
];
*/

console.log("data =", data);
console.log("num =", num);
console.log("");

var result = balancer(data, num);
console.log("result =", result);

function balancer(data, num) {
	var result = Array(num).fill([]);
	var totals = Array(num).fill(0);

	for (var i = 0; i < data.length; i++) {
		var ii = totals.indexOf(Math.min.apply(null, totals));
		result[ii].push(data[i]);
		totals[ii] += data[i];
	}

	console.log("totals =", totals);
	return result;
}

Answer 1

類似の問題：

• Divide 1 to n into two groups with minimum sum difference

（1以上n以下の整数を、それぞれのグループの合計の差が最小になるような2つのグループに分けよ。）

の回答コード例を参考にして、以下を作成してみました。

const mean = data.reduce((total, v) => total + v) / num;  
const groups = [[], [], []];
  
let group1Sum = mean;
let group2Sum = mean;

for (let v of data) {  
  if (group1Sum - v >= 0) {
    groups[0].push(v);
    group1Sum -= v;
  } else if (group2Sum - v >= 0) {
    groups[1].push(v);
    group2Sum -= v;
  } else {
    groups[2].push(v);
  }
}

// 結果の出力
groups.forEach(a => {  
  const sum = a.reduce((s, v) => s + v);
  console.log(a, sum);  
});

出力結果：

[6,6,6] 18

[6,5,5,2] 18
[4,3,3,3,2,2,2] 19

???? codepen

所与のdataの内容がどのようなものであっても、上記のコードのほうがご質問にある

とりあえず単純に、配列の先頭から順に常に合計値が一番小さいグループに加算するというロジック

よりも良い結果を出すことができる（少なくとも、より悪い結果にはならない）ことの証明はすぐは考えつきませんでした。ですので参考に留めていただければと思います。

Comments

[miu_ras]

コードありがとうございます。

ご提示のコードだとデータの後ろに調整をきかせやすい細かい数字があるときにはうまくいく可能性が高まる、そうでない場合には失敗する可能性が高くなるという感じですね。前のグループに大きい数字を詰めていくことになるので、偏りが大きくなり、調整がききにくくなってしまいます。

データが[6, 6, 6, 6, 5, 5, 4, 3, 3]のときには[12, 12, 20]となってしまい、全然ダメでした。ちなみに私のコードでは[15, 15, 14]となりました。グループが2つの場合用で、それ以外には通用しない方法かもしれませんね。

Answer 2

動的計画法(Dynamic Programming)向きの問題のように見えます。
探せば見つかるかもしれません。

Comments

[miu_ras]

動的計画法…。イチから勉強するのは少し大変そうですが、少し勉強してみます。
ありがとうございました。