功能来确定组合的值是小于一个阈值

Question

我想开发一个优化功能，将确定哪些元素列表中的双打时加在一起将小于指定的阈值。元素可以多次使用。

例如，如果我的元素列表

{1,3,7,10} 

，我的阈值是20我希望我的结果是

1 
3 
7 
10 
10, 10 
10, 7 
10, 7, 3 
10,7,1 
10,7,1,1 
10,7,1,1,1 
7,7 
7,7,3 
7,7,1 
7,7,1,1 
7,7,1,1,1 
... 

我想到的是，这个问题的答案可能会是一个递归调用，也许可以在教科书中找到，但我不知道如何恰当地将问题短语找出答案。将不胜感激这一组专家的帮助。

Answer 1

该程序的工作原理，似乎是最简单的解决方案。所有结果按升序排序。

private static final HashSet<ArrayList<Double>> lists = 
     new HashSet<ArrayList<Double>>(); // all of the combinations generated 

    private static final double[] elements = {10, 7, 3, 1}; 

    public static void main(String[] args) { 
    combine(20, new ArrayList<Double>()); 
    for (ArrayList<Double> set : lists) { 
     System.out.println(set); 
    } 
    } 

    private static void combine(final double limit, ArrayList<Double> stack) { 
    // iterates through the elements that fit in the threshold 
    for (double item : elements) { 
     if (item < limit) { 
     final ArrayList<Double> nextStack = new ArrayList<Double>(stack); 
     nextStack.add(item); 
     // a sort is necessary to let the HashSet de-dup properly 
     Collections.sort(nextStack); 
     lists.add(nextStack); 
     combine(limit - item, nextStack); 
     } 
    } 
    } 

虽然这种类型的组合问题产生了许多结果。如果您比代码可读性和简单性更关心性能，我可以进一步优化。

C＃：

static void Main(string[] args) 
    { 
     Run(); 
    } 

    static public void Run() 
    { 
     Combine(20, new List<Double>()); 
     foreach (List<Double> set in lists) 
     { 

      Debug.Print(set.ToString()); 
     } 
    } 
    private static HashSet<List<Double>> lists = 
     new HashSet<List<Double>>(); // all of the combinations generated 

    private static double[] elements = { 10, 7, 3, 1 }; 

    private static void Combine(double limit, List<Double> stack) 
    { 
     // iterates through the elements that fit in the threshold 
     foreach (double item in elements) 
     { 
      if (item < limit) 
      { 
       List<Double> nextStack = new List<Double>(stack); 
       nextStack.Add(item); 
       // a sort is necessary to let the HashSet de-dup properly 
       nextStack.Sort(); 
       lists.Add(nextStack); 
       Combine(limit - item, nextStack); 
      } 
     } 
    } 

Answer 2

我不知道是否需要针对检测正确重复的条目，但此代码应工作Sort()：一次

private List<int[]> CombinedElementsInArrayLessThanValue(int[] foo, int value) 
    { 
     List<int[]> list = new List<int[]>(); 

     for (int i = 0; i < foo.Length; i++) 
     { 
      List<int> start = new List<int>(); 
      start.Add(foo[i]); 
      start.Sort(); 
      int[] clone = start.ToArray(); 
      if (start.Sum() < value && !list.Contains(clone)) 
      { 
       list.Add(clone); 
       CombinedElementsInArrayLessThanValue(foo, value, start, list); 
      } 
     } 
     return list; 
    } 

    private void CombinedElementsInArrayLessThanValue(int[] foo, int value, List<int> partial, List<int[]> accumulate_result) 
    { 
     for (int i = 0; i < foo.Length; i++) 
     { 
      List<int> clone = new List<int>(partial); 
      clone.Add(foo[i]); 
      clone.Sort(); 
      int[] array = clone.ToArray(); 
      if (clone.Sum() < value && !accumulate_result.Contains(array)) 
      { 
       accumulate_result.Add(array); 
       CombinedElementsInArrayLessThanValue(foo, value, clone, accumulate_result); 
      } 
     } 
    } 

Answer 3

过程中的一个项目列表中，并让递归完全处理一个项目以缩短递归的“深度”。

public static List<int[]> Combine(int[] elements, int maxValue) 
{ 
    LinkedList<int[]> result = new LinkedList<int[]>(); 
    List<int> listElements = new List<int>(elements); 
    listElements.Sort(); 
    Combine(listElements.ToArray(), maxValue, new int[0], result); 
    return result.ToList(); 
} 

private static void Combine(int[] elements, int maxValue, int[] stack, LinkedList<int[]> result) 
{ 
    if(elements.Length > 0 && maxValue >= elements[0]) 
    {    
     var newElements = elements.Skip(1).ToArray(); 
     for (int i = maxValue/elements[0]; i > 0; i--) 
     { 
      result.AddLast(stack.Concat(Enumerable.Repeat(elements[0], i)).ToArray()); 
      Combine(newElements, maxValue - i*elements[0], result.Last(), result); 
     } 
     Combine(newElements, maxValue, stack, result); 
    } 
}