コンテナに値を均等に分配するアルゴリズムですか？

Question

誰も、設定された数のコンテナに数値を均等に分配する方法を知っていますが、コンテナの合計値が可能な限り同じであることを確認してください。

編集：「できるだけ早く」とは、X個のコンテナに分散されている場合、各コンテナの合計が合計平均に近いことを意味します。

今は単純に数値の配列をソートして（降順）、値を無視してコンテナに分配します。 3つのコンテナに分配された1000,200,20,1000のセットは、[2000]、[200]、[20]に等しくなります。私が何をしたいか

は次のとおりです。

Example 

Set of numbers: 10 30 503 23 1 85 355 
If I were to distribute these into three containers I would just pick the highest first and then distribute them as I go, like this: 
Cont 1 = 503 
Cont 2 = 355 
Cont 3 = 85 + 30 + 23 + 10 + 1 

This will give the best possible distribution that you can get with the values provided. 

しかし、私は、コードでこれを表現するためのきちんとした方法を知りません。

アイデア？

Answer 1

オブジェクトのサイズに大きなばらつきがあり、の鋳鉄要件はでなければならないと思いますか？もしそうなら、これは現実的ではありません。

しかし、良いニュースは、NP完全な理論では、実際の世界では非常に簡単です！データポイントの数が比較的少ない場合は、インテリジェントな（ただし完全な）検索を行い、世界的に最適なソリューションを見つけることができます。

値の分散が非常に小さい場合 適切に動作するデータセットがある場合は、すべてのコンテナを正確に均等に塗りつぶすソリューションをすばやく見つけることができます。もしそうなら、これは明らかに可能な最良の答えです。これは、非常に大きなデータセットでもうまくいく可能性があります。 （私はあなたがここで望んでいるのは、最後に簡単に整理するために使用できる小さな値がたくさんあるデータセットだと思います）。

だから、あきらめないでください！まず、データをソートし、データポイントを最大から最小まで考慮します。各段階で、現在最も小さいコンテナに次の値を割り当てます。これはおそらくすべてのケースで最適なソリューションを提供するわけではありませんが、実際にはかなり合理的かもしれません。

ソート1000, 200, 20, 1000は、1000, 1000, 200, 20となります。このアルゴリズムでは、次のような結果が得られます。

1000  = 1000 
1000  = 1000 
200 +20 = 220 

これは最適な解決方法ですが、必ずしもそうであるとは限りません。

====

あなたが喜んで、より複雑なアルゴリズムを試すことができている場合は、the partition problemを検索：

パーティションの問題はNP完全であるが、 擬似多項式があります多くの場合に問題を解決する ヒューリスティックがあり、最適には またはおよそのいずれかです。このため、「最も簡単な ハード・トラブル」と呼ばれています。

パーティション問題の最適化バージョンがあります。これは、マルチセットSを2つのサブセットS1、S2に分割し、S1の要素の合計とS2の要素の合計の差が最小になるようにすることです。

Answer 2

興味深い。このCプログラムはこれまで予想されていた結果を出すようです。それはデータを並べ替えることから始まり、次にnのコンテナの場合は、すぐにnのそれぞれの番号が格納されます。 （実際にそのステップを省略することができます）。次に、最大の残りの数値から最小の値まで、その数値を加算すると、との差が最小となるコンテナが見つかる。これは高い値から低い値へと変化するため、各数値は最適なコンテナに格納されます。他の数値はすべて低くなりますので、それらの差はさらに大きくなります。

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#include <limits.h> 

int sort_numeric (const void *a, const void *b) 
{ 
    return *((int *)a) - *((int *)b); 
} 

int main (int argc, char **argv) 
{ 
    int list[] = { 10, 30, 503, 23, 1, 85, 355 }; 
    int i,j, nnumber, ncontainer, total, avgPerContainer, nextError, smallestError, containerForSmallest; 
    int *containers, *errors; 

    ncontainer = 3; 

    nnumber = sizeof(list)/sizeof(list[0]); 

    qsort (list, nnumber, sizeof(list[0]), sort_numeric); 

    containers = (int *)malloc(ncontainer * sizeof(int)); 
    for (i=0; i<ncontainer; i++) 
     containers[i] = 0; 

    errors = (int *)malloc(ncontainer * sizeof(int)); 
    for (i=0; i<ncontainer; i++) 
     errors[i] = 0; 


    printf ("input:"); 
    for (i=0; i<nnumber; i++) 
    { 
     printf (" %d", list[i]); 
    } 
    printf ("\n"); 

// how much is to be in each container? 
    total = 0; 
    for (i=0; i<nnumber; i++) 
     total += list[i]; 

// this will result in a fraction: 
//  avgPerContainer = total/ncontainer; 
// so instead we'll use 'total' and *keeping in mind* 
// that the number needs to be divided by ncontainer 
    avgPerContainer = total; 

    printf ("per container: ~%d\n", (2*avgPerContainer+ncontainer)/(2*ncontainer)); 

// start by putting highest values into each container 
    for (i=0; i<ncontainer; i++) 
     containers[i] += list[nnumber-ncontainer+i]; 
// .. remove from list .. 
    nnumber -= ncontainer; 

// print current totals 
    for (i=0; i<ncontainer; i++) 
    { 
     errors[i] = containers[i]*ncontainer - avgPerContainer; 
     printf ("#%d: %d, error = %d/%d ~ %+d\n", i, containers[i], errors[i], ncontainer, (2*errors[i]+ncontainer)/(2*ncontainer)); 
    } 

    printf ("remaining:"); 
    for (i=0; i<nnumber; i++) 
    { 
     printf (" %d", list[i]); 
    } 
    printf ("\n"); 

// add the remainders 
    for (i=nnumber-1; i>=0; i--) 
    { 
     smallestError = INT_MAX; 
     containerForSmallest = 0; 
     for (j=0; j<ncontainer; j++) 
     { 
      nextError = (containers[j] + list[i]) - avgPerContainer; 
      if (nextError < smallestError) 
      { 
       containerForSmallest = j; 
       smallestError = nextError; 
       printf ("error for %d, %d + %d, is %+d\n", j, containers[j], list[i], smallestError); 
      } 
     } 
     printf ("we put %d into #%d\n", list[i], containerForSmallest); 
     containers[containerForSmallest] += list[i]; 
    } 

    for (i=0; i<ncontainer; i++) 
    { 
     printf ("#%d: %d, error = %d/%d ~ %+d\n", i, containers[i], containers[i]*ncontainer - avgPerContainer, ncontainer, (2*(containers[i]*ncontainer - avgPerContainer)+ncontainer)/(2*ncontainer)); 
    } 

    return 0; 
}