各グループの合計が平均に最も近いように、1行の行をN個のグループに分割する方法は？

Question

私は次のような問題があります。私は、各グループの数の合計がこれらの合計の平均にいくらかのメトリックで最も近くなるように、線をN個のグループに分割する必要があります。実際のメトリックは重要ではありません。最も単純な解決策のどれにつながるかに応じて、絶対差の合計や分散などを最小限に抑えることができます。

同様の問題はNP Hardであるセットのパーティショニングです。しかし、ここではグループには連続する数字をパックする必要があるという追加の制約があるため、ブルートフォース検索を含まないソリューションが存在する可能性があります。数字は大きい。

EDIT

例：

数：1 2 3 4 5 6 7 8 9 10、我々は絶対差の総和を最小化したいとしましょう3グループ

に分割する必要があります（悲しい）。

グループ：（1）1 2 3 4 5 6（合計= 21）。 （2）7 8（合計= 15）; （3）9 10（合計= 19）

平均=（21 + 15 + 19）/ 3 = 18.33、SAD = 21-18.33 + 18.33-15 + 19-18.33 = 6.67 < - これは私たちが望むものです。最小化する。

Answer 1

合計が何であるべきか分かったら、この合計に近いグループを作成できます。メトリックが良い場合は、バイナリ検索を使用して実際の合計が何であるかを調べることができます。あなたが特定の合計を目指しているときは、グループの合計が合計サイズを超えるまで、グループに数値を追加するリストを通過することができます。次に、この最後の整数を取るか、取らない。これを行っているリスト全体を調べて、どのグループの合計が合計から最もずれているかを確認します。次に、偏差内に入るグループサイズの組み合わせを試してリストに戻ってください。十分に速くなければなりません。それ以外の場合は動的プログラミングを使用します。

Answer 2

私はどこから来ているのかと思います。私は数字の順番にそれを考えるプログラマーとして、私は一緒に速やかにバレンタインようなものを入れていると私は食事のために出て行くよ:)ここでは簡易版である：私は一緒にこれをすぐに入れている

a = all numbers added together 
b = number of groups 
m = a/b (value is mean) 

c = array(a)DES (add all numbers to an array in decending order) 

foreach c 
    if((m-(c[0] + c[1])) < (m-(c[0])) 
     if((m-(c[0] + c[1] + c[2])) < (m-(c[0] + c[1]))) 
     else 
     g1 = c[0],c[1] 
     c = c - (c[0],c[1]) 

    else 
    g1 = c[0] 
    c = c - c[0] 

foreach c 
    if((m-(c[0] + c[1])) < (m-(c[0])) 
    else 
    g2 = c[0] 

正確ではないかもしれませんが、うまくいけばシーケンスと手順を見ることができます。それぞれの 'foreach'ループと同様に、すべての 'c'値が動的に選択されます。最後の数字を処理して平均値に最も近い値に加算するには、最後にforeachステートメントが必要です。

ハッピーバレンタインデー！

Answer 3

ここでは、（完全にはテストされていませんが）JavaScriptソリューションがあります。

本質的にダイナミックスクリプトを使用して、brute-force stacked for-loops（順序付けられた組み合わせ）を構築し、アレイ内の各グループの開始インデックスを取得します。

var A = [1,2,3,4,5,6,7,8,9,10]; 
var G = 3; 
function find(line, groups) { 
    var length = line.length; 
    var mean = line.sum()/groups; 
    var temp = [0]; 
    var bestsad = 4294967295; 
    var beststarts = []; 
    var dynamic = "var x0 = 0; "; 
    for(var i=1; i<groups; i++) { 
     dynamic += "for(var x" + i + "=x" + (i-1) + "+1;x" + i + "<" + length + ";x" + i + "++) "; 
     temp.push("x" + i); 
    } 
    dynamic += "{ var sad = getSAD(line, mean, [" + temp.join(",") + "]);"; 
    dynamic += "if(sad < bestsad) { bestsad = sad; beststarts = [" + temp.join(",") + "] ;} }" 
    eval(dynamic); 
    console.log("Best SAD " + bestsad); 
    console.log("Best Start Indexes " + beststarts); 
    return beststarts; 
} 
function getSAD(line, mean, starts) { 
    var sums = []; 
    var sad; 
    for(var i = 0; i < starts.length-1; i++) 
    { 
     var idx = i; 
     sums.push(line.slice(starts[idx], starts[i+1]).sum()); 
    } 
    sums.push(line.slice(starts[starts.length-1]).sum()); 
    sad = sums.sad(mean); 
    return sad; 
} 

Array.prototype.sum = function() { 
    var result = 0; 
    for(var i=0; i<this.length; i++) 
     result += this[i]; 
    return result; 
} 
Array.prototype.sad = function(mean) { 
    var result = 0; 
    for(var i=0; i<this.length; i++) 
     result += Math.abs(this[i] - mean); 
    return result; 
} 
find(A, G); 

ここVARダイナミック変数/文字列は/実行を保持していることをどのようなスクリプトがあります。

var x0 = 0; 
for(var x1=x0+1;x1<10;x1++) 
for(var x2=x1+1;x2<10;x2++) { 
    var sad = getSAD(line, mean, [0,x1,x2]); 
    if(sad < bestsad) { 
    bestsad = sad; 
    beststarts = [0,x1,x2] ; 
    } 
} 

なぜグループインデックスベクトル+再帰を使用しないのですか？このタイプの再帰的問題に対しては、反復的方法が最適である。間違いなく、動的スクリプトのオーバーヘッド（および複雑さの増加）は、小さな配列のメリットを無効にしますが、実際のデータ（大きな配列）を使用すると、

Answer 4

これは興味深い問題です。私は答えを説明するために1..10の数字を3つのグループに分けてあなたの例を使用します。このソリューションは、任意の数のセットと任意の数のグループに適用されます。 sourseのうち、数字の集合のサイズが大きいときは、ブルートフォースのアプローチを使用できないことがあります。それでも、大量の数字は同様の方法で扱うことができますが、それ以降はそれを扱うことができます。

私たちはM個の連続した数字（1.M）がセット内にあり、それらをN個のグループに分けたいとします。

最初に決定するのは、各グループの合計を比較する値です。これは、単純にグループの数で除算された数の集合の和N.

例のsumOf（1..M）= 55とN = 3のため、55/3 = 18.33はそれぞれグループは合計する必要があります。グループ合計と18.33の差を最小にしたいとします。

もう1つの例として、数字セット1..20を2つのグループに分けたい場合は、グループ合計とsumOf （1..20）= 210 2つのグループで割る= 210/2 = 105

次のステップは、すべての可能なグループを見つけることです。これは、連続する数字を含む子孫の制限を除いた別の興味深い問題です。グループの組み合わせの合計数は、あなたが期待するほど多くはありません。

組み合わせを見つけることは再帰的な問題であり、一般の方程式を解くのは簡単です。

簡単なケースから始めることができます。セット内の10個の数字の組み合わせ（1..10）。まあ、1つのグループしかありません。数字（1..10）

ここでは、10個の数字に2つのグループの組み合わせがいくつありますか。答え、すなわち

(1),(2..10) 
(1..2) (3..10) 
(1..3) (4..10) 
(1..4) (5..10) 
(1..5) (6..10) 
(1..6) (7..10) 
(1..7) (8..10) 
(1..8) (9..10) 
(1..9) (10) 

そこで、サイズMのセットは、グループのM-1の組み合わせを有する、M-1、10-1 = 9です。これが再帰の基礎です。

10個の数字に3つのグループの組み合わせがいくつありますか。

まあ、最初のグループは最初のグループとしてこれらのいずれかを考えると、次の

(1),(1..2),(1..3) ,(1..4) ,(1..5),(1..6) ,(1..7) ,(1..8) 

のいずれかになり、2基の組み合わせは、残りの数字に存在するどのように多く出て作業することができます。

3つの最初のグループを=（1）とします。 9つの数字が残っており、これらが2つのグループの9-1 = 8つの異なる組み合わせを作ることができることを知っている。 3つの最初のグループ=（1..5）とする。 5つの数字が残っており、これらは5-1 = 4つの異なる2つのグループのグループを作ることができます。

ので、合計で我々は（SumOf（1..8）を与える

(1) -> 8 combinations 
(1..2) -> 7 combinations 
(1..3) -> 6 combinations 
(1..4) -> 5 combinations 
(1..5) -> 4 combinations 
(1..6) -> 3 combinations 
(1..7) -> 2 combinations 
(1..8) -> 1 combinations 

、または一般的に合計（1..M-2）、基の組み合わせを持っています。SumOf（1 ..8）= 8 * 9/2 = 36

したがって、各グループに連続する数字が含まれている10個の数字に3つのグループの36の組み合わせがあります。

を3つのグループに分けて100個のグループに分けてsumOf（1..98）= 98 * 99/2 = 4851個のグループを組み合わせると、Mが増えるほどMの値が増えますブルートフォース法は不可能かもしれない。

上記のアプローチを使用して、単純な再帰アルゴリズムを設計して、セット（1..M）内のグループのすべての組み合わせを取得することができます。

また、一連のM個のグループ内の任意の数N個のグループに対して簡単な方程式を解くことができます。たとえば、10の数字で4つのグループに移動した場合、最初のグループが（1..3）のような状況があり、残りの7つのグループの3つのグループの組み合わせが見つかります。合計（1..M-2）=合計（1..5）などがあります。

とにかく、問題に戻ってください。あなたはグループのすべての組み合わせを持っているので、グループを反復して各組み合わせのSADを計算し、SADを最小にするものを選ぶことができます。

組み合わせ数が非常に多く、それぞれの組み合わせを見ることができない場合は、ランダムに選択するグループにブートストラップするか、ランダムに選択した組み合わせから始めてあるグループから別のグループにランダムに番号を移動し、最も低いSADを持つグループを保持します。 SADのそれ以上の改善が見られなくなるまで、このステップを続けます。

@Robert Kingが示唆するように、1つの組み合わせから始めて、あるグループから別のグループに番号を移動することで改善することができます。

Answer 5

ソート順に配列し、 は和をループ上 反復を格納する3つの数値を有し、最小の合計に現在の数を追加 答えは（10,5,4）、（9,6,3）であり、 （8,7,2,1）

#include<iostream> 
#include<stdio.h> 
#include <algorithm> 

using namespace std; 
int maximum(int x, int y, int z) { 
int max = x; /* assume x is the largest */ 

if (y > max) { /* if y is larger than max, assign y to max */ 
    max = y; 
} /* end if */ 

if (z > max) { /* if z is larger than max, assign z to max */ 
    max = z; 
} /* end if */ 

return max; /* max is the largest value */ 
} 

int main() 
{ 
int array[] = {1 ,2, 3, 4, 5, 6, 7, 8, 9, 10}; 
int size = sizeof(array)/sizeof(array[0]); 
int part1=0; 
int part2=0; 
int part3=0; 

sort(array,array+size,greater<int>()); 
for(int x=0;x<size;x++) 
{ 
    if(part1 < part2 && part1 < part3) 
    { 
     part1 +=array[x]; 
    }else if(part2 < part3){ 
     part2 +=array[x]; 
    }else{ 
     part3 +=array[x]; 
    } 
} 

printf("first part1 = %d\n",part1); 
printf("first part2 = %d\n",part2); 
printf("first part3 = %d\n",part3); 

printf("-------------------------------\n"); 
printf("largest number = %d\n",maximum(part1,part2,part3)); 

}