組合算法

Question

Length = input Long(can be 2550, 2880, 2568, etc) 
List<long> = {618, 350, 308, 300, 250, 232, 200, 128} 

該方案需要很長的值，我們必須找到從其中當添加給我一個輸入結果（相同的值，可以使用兩次）以上列表中的可能的組合，特別是長值。可以有+/- 30的差異。

最大的數字必須用得最多。

例：長度= 868 對於這種組合可以是

組合1 = 618 + 250

組合2 = 308 + 232 + 200 128

正確組合將是組合1

但也應該有不同的組合。

public static void Main(string[] args) 
    { 
     //subtotal list 
     List<int> totals = new List<int>(new int[] { 618, 350, 308, 300, 250, 232, 200, 128 }); 

     // get matches 
     List<int[]> results = KnapSack.MatchTotal(2682, totals); 

     // print results 
     foreach (var result in results) 
     { 
      Console.WriteLine(string.Join(",", result)); 
     } 

     Console.WriteLine("Done.");    
    } 

internal static List<int[]> MatchTotal(int theTotal, List<int> subTotals) 
    { 
     List<int[]> results = new List<int[]>(); 
     while (subTotals.Contains(theTotal)) 
     { 
      results.Add(new int[1] { theTotal }); 
      subTotals.Remove(theTotal); 
     } 

     if (subTotals.Count == 0) 
      return results; 

     subTotals.Sort(); 

     double mostNegativeNumber = subTotals[0]; 
     if (mostNegativeNumber > 0) 
      mostNegativeNumber = 0; 

     if (mostNegativeNumber == 0) 
      subTotals.RemoveAll(d => d > theTotal); 

     for (int choose = 0; choose <= subTotals.Count; choose++) 
     { 
      IEnumerable<IEnumerable<int>> combos = Combination.Combinations(subTotals.AsEnumerable(), choose); 

      results.AddRange(from combo in combos where combo.Sum() == theTotal select combo.ToArray()); 
     } 
     return results; 
    } 


public static class Combination 
{ 
     public static IEnumerable<IEnumerable<T>> Combinations<T>(this IEnumerable<T> elements, int choose) 
     { 
      return choose == 0 ? 
       new[] { new T[0] } : 
       elements.SelectMany((element, i) => 
        elements.Skip(i + 1).Combinations(choose - 1).Select(combo => (new[] { element }).Concat(combo))); 
     } 
} 

我已經使用了上面的代碼，它可以更簡化，再次在這裏我也得到了獨特的價值。值可以被使用任意次數。但是，最大的數量必須得到最優先考慮。

我有一個驗證，以檢查總和是否大於輸入值。即使在那裏，邏輯也會失敗。

Answer 1

您顯示的算法假定列表按升序排序。如果不是，那麼你首先必須在O（nlogn）時間內對列表進行排序，然後執行算法。

此外，它假定您只考慮配對的組合，並在第一場比賽中退出。 如果您想要查找所有組合，則不是「中斷」，而是輸出組合並遞增startIndex或遞減endIndex。此外，您應該檢查範圍（targetSum - 30 to targetSum + 30），而不僅僅是確切的值，因爲問題表明允許出現誤差範圍。

這是根據我的最佳解決方案，因爲它的複雜性是O（nlogn + n），包括排序。

Answer 2

V4 - 遞歸方法，對螺紋

它的工作原理（在VS測試）使用堆棧結構，而不是棧幀的，但也可能有剩餘的一些錯誤。

static int Threshold = 30; 
    private static Stack<long> RecursiveMethod(long target) 
    { 
     Stack<long> Combination = new Stack<long>(establishedValues.Count); //Can grow bigger, as big as (target/min(establishedValues)) values 
     Stack<int> Index = new Stack<int>(establishedValues.Count); //Can grow bigger 
     int lowerBound = 0; 
     int dimensionIndex = lowerBound; 
     long fail = -1 * Threshold; 
     while (true) 
     { 
      long thisVal = establishedValues[dimensionIndex]; 
      dimensionIndex++; 
      long afterApplied = target - thisVal; 

      if (afterApplied < fail) 
       lowerBound = dimensionIndex; 
      else 
      { 
       target = afterApplied; 
       Combination.Push(thisVal); 
       if (target <= Threshold) 
        return Combination; 
       Index.Push(dimensionIndex); 
       dimensionIndex = lowerBound; 
      } 

      if (dimensionIndex >= establishedValues.Count) 
      { 
       if (Index.Count == 0) 
        return null; //No possible combinations 

       dimensionIndex = Index.Pop(); 
       lowerBound = dimensionIndex; 
       target += Combination.Pop(); 
      } 
     } 

    } 

也許V3 - 建議爲有序解決方案試圖

雖然這是沒有選擇的答案的相關問題每一個組合，我相信這是一個很好的方法 - https://stackoverflow.com/a/17258033/887092（，否則你可以嘗試選擇的答案（儘管輸出只是集合中的2個項目，而不是最多n個項目）） - 它會列舉每個選項，包括相同值的倍數。 V2可以工作，但會比有序的解決方案稍微低效，因爲可能會多次嘗試相同的失敗嘗試。

V2 - 隨機選擇 - 將能夠重複使用了相同的號碼

我使用隨機的「智能」，允許計算機蠻力解決方案的粉絲。分發也很容易 - 因爲兩個線程在同一時間嘗試不存在狀態依賴關係。

static int Threshold = 30; 

    public static List<long> RandomMethod(long Target) 
    { 
     List<long> Combinations = new List<long>(); 
     Random rnd = new Random(); 

     //Assuming establishedValues is sorted 
     int LowerBound = 0; 
     long runningSum = Target; 

     while (true) 
     { 
      int newLowerBound = FindLowerBound(LowerBound, runningSum); 

      if (newLowerBound == -1) 
      { 
       //No more beneficial values to work with, reset 
       runningSum = Target; 
       Combinations.Clear(); 
       LowerBound = 0; 
       continue; 
      } 


      LowerBound = newLowerBound; 

      int rIndex = rnd.Next(LowerBound, establishedValues.Count); 
      long val = establishedValues[rIndex]; 
      runningSum -= val; 
      Combinations.Add(val); 

      if (Math.Abs(runningSum) <= 30) 
       return Combinations; 
     } 
    } 

    static int FindLowerBound(int currentLowerBound, long runningSum) 
    { 
     //Adjust lower bound, so we're not randomly trying a number that's too high 
     for (int i = currentLowerBound; i < establishedValues.Count; i++) 
     { 
      //Factor in the threshold, because an end aggregate which exceeds by 20 is better than underperforming by 21. 
      if ((establishedValues[i] - Threshold) < runningSum) 
      { 
       return i; 

      } 
     } 
     return -1; 
    } 

V1 - 有序的選擇 - 將不能再使用了相同的號碼

1. 添加這個非常方便的擴展功能（如使用二進制算法來找到所有組合）：

   //Make sure you put this in a static class inside System namespace 
   public static IEnumerable<List<T>> EachCombination<T>(this List<T> allValues) 
   { 
       var collection = new List<List<T>>(); 
       for (int counter = 0; counter < (1 << allValues.Count); ++counter) 
       { 
        List<T> combination = new List<T>(); 
        for (int i = 0; i < allValues.Count; ++i) 
        { 
         if ((counter & (1 << i)) == 0) 
          combination.Add(allValues[i]); 
        } 
   
        if (combination.Count == 0) 
         continue; 
   
        yield return combination; 
       } 
   } 
   

2. 使用功能

   static List<long> establishedValues = new List<long>() {618, 350, 308, 300, 250, 232, 200, 128, 180, 118, 155}; 
   
   //Return is a list of the values which sum to equal the target. Null if not found.   
   List<long> FindFirstCombination(long target) 
   { 
       foreach (var combination in establishedValues.EachCombination()) 
       { 
        //if (combination.Sum() == target) 
         if (Math.Abs(combination.Sum() - target) <= 30) //Plus or minus tolerance for difference 
         return combination; 
       } 
   
       return null; //Or you could throw an exception 
   } 
   

3. 測試解決方案，如果列表排序，你只需要兩個元素的組合

   var target = 858; 
   var result = FindFirstCombination(target); 
   bool success = (result != null && result.Sum() == target); 
   
   //TODO: for loop with random selection of numbers from the establishedValues, Sum and test through FindFirstCombination