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, 5, 4), (3, 6), (9), (7), (4, 3), (8, 2), (1, 6, 3), (7)

谁能帮我解决问题？我正在考虑一些递归实现。我在正确的轨道上吗？

编辑

好的，因为我不能完全按照我的意愿解释这个问题:) 让我们让它更简单。如何生成 sum <= N 的所有子列表，并且列表的每个数字只能包含一次。我会自己做剩下的工作。

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 回答