4

ArrayList<int>組み合わせて使用​​できるすべての番号が含まれています。異なる長さ（整数の数）のこれらの数の可能なすべての組み合わせを生成したいのですが、すべてがNに最も近い合計を持っている必要がありますが、<= N（Nは入力数です）。リストのすべての番号は一度だけ使用する必要があります。

例

N = 10
list = {1, 5, 4, 3, 6, 9, 7, 4, 3, 8, 2, 1, 6, 3, 7}

1つの組み合わせは、（1、5、4）、（3、6）、（9）、（7）、（4、3）、（8、2）、（1、6、3）、（7）になります。

誰かが解決策を手伝ってくれますか？再帰的な実装を考えています。私は正しい方向に進んでいますか？

編集

OK、私はこの問題を私が望むように正確に説明することができないので:)それをもっと簡単にしましょう。合計がN未満で、リストの各番号を1回だけ含めることができるすべてのサブリストを生成する方法。残りの作業は自分で行います。

4

2 に答える 2

1

有限集合Sの単純なkの組み合わせは、Sのk個の異なる要素のサブセットです。サブセットを指定しても、それらは特定の順序で配置されません。

CombinatoricsLibを使用できます。CombinatoricsLibは、組み合わせオブジェクトを生成するためのJavaライブラリです。https://code.google.com/p/combinatoricslib/

これを使用する：

    public static void main(String[] args) {

           // Create the initial vector
           ICombinatoricsVector<Integer> initialVector = Factory.createVector(
              new Integer[]  {1, 5, 4, 3, 6, 9, 7, 4, 3, 8, 2, 1, 6, 3, 7} );          

           int subsetMaxSize = 5;
           int upperLimit = 10;  
           int lowerLimit = 8;
           for(int i = 1; i <= subsetMaxSize; i++)
           {
               Generator<Integer> gen = Factory.createSimpleCombinationGenerator(initialVector, i);
               for (ICombinatoricsVector<Integer> combination : gen)
               {
                   int sum = vectorSum(combination);
                   if(validateSum(sum, lowerLimit, upperLimit))
                       printVector(combination);
               }   
           }
    }

    public static boolean validateSum(Integer value, Integer lowerLimit, Integer upperLimit)
    {
        if(value <= upperLimit && value > lowerLimit)   
            return true;
        return false;           
    }

    public static Integer vectorSum(ICombinatoricsVector<Integer> vect)
    {
        Integer sum = 0;    
        for(int i = 0; i < vect.getSize(); i++) 
            sum += vect.getValue(i);
        return sum;
    }

    public static void printVector(ICombinatoricsVector<Integer> vect)
    {
        String output = ""; 
        for(int i = 0; i < vect.getSize(); i++)
            output += vect.getValue(i) + ", ";
        System.out.println(output);
    }

出力を返します

9, 
1, 9, 
1, 8, 
5, 4, 
5, 4, 
4, 6, 
4, 6, 
3, 6, 
3, 7, 
3, 6, 
3, 7, 
6, 4, 
6, 3, 
6, 3, 
9, 1, 
7, 3, 
7, 2, 
7, 3, 
4, 6, 
3, 6, 
3, 7, 
8, 2, 
8, 1, 
2, 7, 
6, 3, 
3, 7, 
1, 5, 4, 
1, 5, 3, 
1, 5, 4, 
1, 5, 3, 
1, 5, 3, 
1, 4, 4, 
1, 3, 6, 
1, 3, 6, 
1, 6, 3, 
1, 6, 2, 
1, 6, 3, 
1, 7, 2, 
1, 7, 1, 
1, 3, 6, 
1, 8, 1, 
1, 2, 6, 
1, 2, 7, 
1, 1, 7, 
1, 6, 3, 
5, 4, 1, 
5, 3, 2, 
5, 3, 1, 
5, 4, 1, 
5, 3, 2, 
5, 3, 1, 
5, 2, 3, 
5, 1, 3, 
4, 3, 3, 
4, 3, 2, 
4, 3, 3, 
4, 4, 2, 
4, 4, 1, 
4, 3, 2, 
4, 3, 3, 
4, 2, 3, 
3, 6, 1, 
3, 4, 3, 
3, 4, 2, 
3, 4, 3, 
3, 3, 3, 
3, 1, 6, 
6, 3, 1, 
6, 2, 1, 
6, 1, 3, 
7, 2, 1, 
4, 3, 2, 
4, 3, 3, 
4, 2, 3, 
3, 1, 6, 
2, 1, 6, 
2, 1, 7, 
1, 6, 3, 
1, 5, 3, 1, 
1, 5, 3, 1, 
1, 5, 2, 1, 
1, 5, 1, 3, 
1, 4, 3, 2, 
1, 4, 3, 1, 
1, 4, 4, 1, 
1, 4, 3, 2, 
1, 4, 3, 1, 
1, 4, 2, 3, 
1, 4, 1, 3, 
1, 3, 4, 2, 
1, 3, 4, 1, 
1, 3, 3, 2, 
1, 3, 3, 3, 
1, 3, 2, 3, 
1, 6, 2, 1, 
1, 4, 3, 2, 
1, 4, 3, 1, 
1, 4, 2, 3, 
1, 4, 1, 3, 
1, 3, 2, 3, 
1, 2, 1, 6, 
4, 3, 2, 1, 
4, 3, 2, 1, 
4, 2, 1, 3, 
3, 4, 2, 1, 
3, 3, 2, 1, 
3, 3, 1, 3, 
3, 2, 1, 3, 
4, 3, 2, 1, 
4, 2, 1, 3, 
3, 2, 1, 3, 
1, 3, 3, 2, 1, 
1, 3, 2, 1, 3, 
1, 3, 2, 1, 3,
于 2013-03-05T14:19:08.563 に答える
0

再帰を使用できますが、元の問題と制約が何であるかがわかれば、より良い解決策がある可能性があります。再帰の場合、次のようになります。

list = {1, 5, 4, 3, 6, 9, 7, 4, 3, 8, 2, 1, 6, 3, 7};
result = {};

function rec(index, max_sum) {
    if(index >= list.length) {
        print result;
        return;
    }
    for each list[i] where i >= index {
        // Case 1 - we take current element and go further
        if(list[i] <= max_sum) {
            result.insert(list[i]);
            rec(index + 1, max_sum - list[i]);
            result.remove(list[i]);
        }

        // Case 2 - we skip current element
        rec(index + 1, max_sum);
    }
}

N = 10;
rec(0, N);

これは、合計が N を超えない数値のすべての可能な組み合わせを生成するだけです。

于 2013-03-05T14:10:43.750 に答える