8

この問題には正式な名前があると確信しています。その名前を知っていると、おそらく解決策を見つけるのに役立ちますが、私にはわかりません。Googleの問題を表現すると、同じではないナップサック問題が指摘され続けます。もの。

いくつかの値Xを取得し、その値を整数のN個のスタックに分割するすべての可能な組み合わせを見つけたいと思います。

私の言い回しが紛らわしい場合のために、ここにX = 4、N=3の例を示します。

Stack -> 1 | 2 | 3 |
----------------------
#1-----> 4 | 0 | 0 |
----------------------
#2-----> 3 | 1 | 0 |
----------------------
#3-----> 2 | 1 | 1 |
----------------------
#4-----> 2 | 2 | 0 |

削除が簡単なため、重複は許容されますが、理想的には計算されません。問題を解決するためのアルゴリズムは完璧ですが、問題を見つけることでさえ名前が付いているので、研究が容易になります。ありがとう。

4

3 に答える 3

5

これらは実際には、削除された回答の注釈としての整数パーティションです。Mathematicaを使う：

IntegerPartitions[4, 3] // PadRight //Grid

出力：

4   0   0
3   1   0
2   2   0
2   1   1

C＃の実装が見つかりませんでしたが、関連する質問がいくつかあります。

整数分割のためのエレガントなPythonコード

Javaの整数パーティション

整数パーティションを生成するためのアルゴリズム

グーグルヒット：

JeromeKelleherによる整数分割アルゴリズム

DanielScoccoによる整数分割アルゴリズム

整数パーティションを生成するための高速アルゴリズム（PDF）（頑丈に見えます）

StonyBrookアルゴリズムリポジトリ-パーティション

于 2012-06-13T17:42:33.987 に答える
2

これはトリックを行うようです：

vector<vector<int> > partitions(int X, int N, int Y)
{
    vector<vector<int> > v;
    if(X<=1 || N==1)
    {
        if(X<=Y)
        {
            v.resize(1);
            v[0].push_back(X);
        }
        return v;
    }
    for(int y=min(X, Y); y>=1; y--)
    {
        vector<vector<int> > w = partitions(X-y, N-1, y);
        for(int i=0; i<w.size(); i++)
        {
          w[i].push_back(y);
          v.push_back(w[i]);
        }
    }
    return v;


   }

int main()
{
    vector<vector<int> > v = partitions(5, 3, 5);
    int i;
    for(i=0; i<v.size(); i++)
    {
        int x;
        for(x=0; x<v[i].size(); x++)
            printf("%d ", v[i][x]);
        printf("\n");
    }
    return 0;
}
于 2012-06-13T17:37:23.613 に答える
1

これは、C＃でのuser434507の回答です。

class Program
{
    static void Main(string[] args)
    {
        var v = Partitions(5, 3, 5);

        for (int i = 0; i < v.Count; i++)
        {
            for (int x = 0; x < v[i].Count; x++)
                Console.Write(v[i][x] + " "); 
            Console.WriteLine();
        }
    }

    static private List<List<int>> Partitions(int total, int stacks, int max)
    {
        List<List<int>> partitions = new List<List<int>>();

        if (total <= 1 || stacks == 1)
        {
            if (total <= max)
            {
                partitions.Add(new List<int>());
                partitions[0].Add(total);
            }

            return partitions;
        }
        for (int y = Math.Min(total, max); y >= 1; y--)
        {
            var w = Partitions(total - y, stacks - 1, y);
            for (int i = 0; i < w.Count; i++)
            {
                w[i].Add(y);
                partitions.Add(w[i]);
            }
        }

        return partitions;
    }
}
于 2012-06-13T18:02:35.400 に答える