algorithm - 生成数字列表的所有组合，其中组合的总和 <= N

Question

我有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)

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

编辑

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

Answer 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,