具有相同權重/值的修改揹包/子集合總和

Question

我正在研究一個必須處理揹包/子集和問題的特例的問題。問題如下：

您有一組隨機大小減小的包大小：{47, 35, 22, ...}。您具有的值就是這樣的小部件數量：#widgets = 33. 查找可以構成捆綁包小部件數量的最少捆綁數量。如果沒有辦法返回等於數量的集合，則返回null。

• 實施例1：
  • 包大小：46，25，12，如圖4所示，3
  • 量：30
  • 返回值：{46：0，25：0，12：2， 4：0,3：2}（束尺寸：束＃）
• 實施例2：
  • 包大小：46，25，12，如圖4所示，3
  • 量：17
  • 返回值：{46：0，25：0，12：0,4：2,3：3}
• 實施例3：
  • 包大小：46，25 ，12，4，3
  • 量：47
  • 返回值：{46：0，25：1，12：1，4：1,3：2}
• 實施例4：
  • 種尺寸：46，25，12，4，3
  • 數量：5
  • 返回值：空

將如何着手這個問題？

我已經在C＃中編寫了一個程序，它能夠完成足夠的工作，但會重置for循環中的索引以轉儲不適用於其餘集合的程序包大小。如果請求發送源文件，它會發送多遠。

請求代碼：

public List<int> BreakDown(List<int> bunSize, int buySize) 
    { 
     List<int> tempBunSize = bunSize.ToList(); 
     tempBunSize.RemoveAll(e => e > buySize); 

     List<int> ammountNeeded = new List<int>(); 
     int result = buySize; 

     for (int index = 0; index < tempBunSize.Count; index++) 
     {  
      int size = tempBunSize[index]; 
      int tempResult = 0; 
      double calcResult = 0; 
      int addAmmount = 0; 

      if (index == tempBunSize.Count - 2) 
      { 
       tempResult = result % size; 

       if ((tempBunSize.Count > 2 || result % tempBunSize[tempBunSize.Count - 1] == 0)) 
       { 
        if (result % size != 0) 
        { 
         ammountNeeded.Add(0); 
         tempResult = result % tempBunSize[tempBunSize.Count - 1]; 

         if (tempResult != 0) 
         { 
          tempResult = result; 
          int sizeInc = 0; 
          while (tempResult != 0) 
          { 
           tempResult = tempResult - size; 
           sizeInc++; 
           if (tempResult < 0) 
           { 
            int decreaseOne = ammountNeeded.First(); 
            ammountNeeded[0] = --decreaseOne; 
            result = result + tempBunSize.First(); 
            if (ammountNeeded[0] <= 0) 
            { 
             tempBunSize.RemoveAt(0); 
             index = 0; 
             ammountNeeded = new List<int>(); 
            } 
            ammountNeeded.Remove(0); 
            --index; 
            break; 
           } 
           if (tempResult % tempBunSize[tempBunSize.Count - 1] == 0) 
           { 
            ammountNeeded.Remove(0); 
            ammountNeeded.Add(sizeInc); 
            ammountNeeded.Add(tempResult/tempBunSize[tempBunSize.Count - 1]); 
            break; 
           } 
          } 
          if (tempResult < 0) continue; 
          break; 
         } 
         else 
         { 
          calcResult = result/tempBunSize[tempBunSize.Count - 1]; 
          addAmmount = (int)Math.Floor(calcResult); 
          ammountNeeded.Add(addAmmount); 
          break; 
         } 
        } 
        else if (result % size == 0) 
        { 
         tempResult = result % size; 
         if (tempResult != 0 && result % tempBunSize[tempBunSize.Count - 1] != 0) 
         { 
          int decreaseOne = ammountNeeded.First(); 
          ammountNeeded.Insert(0, --decreaseOne); 
          result = result + tempBunSize.First(); 
          continue; 
         } 
         else 
         { 
          calcResult = result/size; 
          addAmmount = (int)Math.Floor(calcResult); 
          ammountNeeded.Add(addAmmount); 

          if (result % size == 0) 
          { 
           ammountNeeded.Add(0); 
           break; 
          } 
          calcResult = result/tempBunSize[tempBunSize.Count - 1]; 
          addAmmount = (int)Math.Floor(calcResult); 
          ammountNeeded.Add(addAmmount); 
          break; 
         } 
        } 
       } 
       else if (tempResult % tempBunSize[tempBunSize.Count - 1] != 0) 
       { 
        tempResult = result; 
        int sizeInc = 0; 
        while (tempResult != 0) 
        { 
         tempResult = tempResult - size; 
         sizeInc++; 
         if (tempResult % tempBunSize[tempBunSize.Count - 1] == 0) 
         { 
          ammountNeeded.Add(sizeInc); 
          ammountNeeded.Add(tempResult/tempBunSize[tempBunSize.Count - 1]); 
          break; 
         } 

        } 
        break; 
       } 
       else if (result == 0) 
       { 
        while (ammountNeeded.Count < bunSize.Count) 
        { 
         ammountNeeded.Add(0); 
        } 
        break; 
       } 
       else 
       { 
        calcResult = result/size; 
        ammountNeeded.Add((int)Math.Floor(calcResult)); 

        calcResult = tempResult/tempBunSize[tempBunSize.Count - 1]; 
        ammountNeeded.Add((int)Math.Floor(calcResult)); 
        break; 
       } 
      } 
      ammountNeeded.Add((int)Math.Floor((decimal)result/size)); 
      result = result % size; 
      if (result == 0) continue; 

     } 

     if (ammountNeeded.Count < bunSize.Count) 
     { 
      ammountNeeded.Reverse(0, ammountNeeded.Count); 
      while (ammountNeeded.Count < bunSize.Count) 
      { 
       ammountNeeded.Add(0); 
      } 
      ammountNeeded.Reverse(0, ammountNeeded.Count); 
     } 
     if (ammountNeeded.FindLast(e => e < 0) < 0 || ammountNeeded.Sum() == 0) 
      return null; 
     return ammountNeeded; 
    } 
} 

Answer 1

曾爲更多的解決方案，並感謝同事和paqogomez的答案，我們得到了正確的代碼，所有的作品一個更好的格式輸出的小變化我的例子和更多！我的同事告訴我，您可以使用堆棧代替遞歸，並使用堆棧來跟蹤位於捆綁列表左側和右側的索引。此代碼使用貪婪暴力解決方案，如果有更快的方式我會感興趣！

C＃代碼：關於這一點，特別感謝所有幫助我的同事和paqogomez一些幫助解決

class Program 
{ 
    public static void Main() 
    { 
     List<int> bundleSizes = new List<int> { 46, 25, 12, 4, 3 }; 
     int quantity = 30; 
     Dictionary<int, int> bundleResults = StackThis(bundleSizes, quantity); 
     Output(bundleSizes, quantity, bundleResults); 

     quantity = 17; 
     bundleResults = StackThis(bundleSizes, quantity); 
     Output(bundleSizes, quantity, bundleResults); 

     quantity = 47; 
     bundleResults = StackThis(bundleSizes, quantity); 
     Output(bundleSizes, quantity, bundleResults); 

     quantity = 5; 
     bundleResults = StackThis(bundleSizes, quantity); 
     Output(bundleSizes, quantity, bundleResults); 

     Console.Read(); 
    } 

    // Reused paqogomez output 
    static void Output(List<int> bundleSizes, int quantity, Dictionary<int, int> bundleResults) 
    { 
     var fullResults = new Dictionary<int, int>(); 
     bundleSizes.ForEach(
      delegate(int e) 
      { 
       var result = 0; 
       if (bundleResults != null) 
        bundleResults.TryGetValue(e, out result); 
       fullResults.Add(e, result); 
      }); 
     Console.WriteLine("Bundle Sizes: {0}", string.Join(",", bundleSizes)); 
     Console.WriteLine("Quantity: {0}", quantity); 
     Console.WriteLine("Returned Value: {0}", bundleResults == null ? "null" : fullResults.Aggregate("", (keyString, pair) => keyString + pair.Key + ":" + pair.Value + ",")); 
    } 

    static private Dictionary<int, int> StackThis(List<int> usableBundle, int currentQuantity) 
    { 
     // Order the list from largest bundle size to smallest size 
     List<int> arrUsableBundles = usableBundle.OrderByDescending(x => x).ToList(); 

     // Key: Bundles | Value: Quantity 
     Dictionary<int, int> hmBundleToQuantity = new Dictionary<int, int>(); 

     // Create the hashmap table structure 
     foreach (int Bundle in arrUsableBundles) 
     { 
      hmBundleToQuantity.Add(Bundle, 0); 
     } 

     // Keep track of our index of the bundles we need to figure out 
     Stack<int> stBundleIndex = new Stack<int>(); 

     // Used to calculate the left and right of bundle list 
     int ixCursor; 

     // Our remaining quantity after calculations 
     int iRemaining; 

     /* 
      This will act as the midpoint of the bundle list 
      Will update the right of the cursor, decrement the 
      cursor, don’t touch the left, and since the loop 
      hasn’t started we’ll consider everything updatable 
      and on the right of the cursor 
     */ 
     stBundleIndex.Push(-1); 

     // Keep working till there is no more ways to solve the solution 
     while (stBundleIndex.Count > 0) 
     { 
      // The current cursor is always removed and needs to 
      // be added back if we want to check it again 
      ixCursor = stBundleIndex.Pop(); 

      iRemaining = currentQuantity; 

      for (int ixBundle = 0; ixBundle < usableBundle.Count; ++ixBundle) 
      { 
       //Left of current scope, values remain the same 
       if (ixBundle < ixCursor) 
       { 
        iRemaining -= (hmBundleToQuantity[usableBundle[ixBundle]] * usableBundle[ixBundle]); 
       } 

       //At the cursor stack scope – decrement current quantity 
       if (ixBundle == ixCursor) 
       { 
        --hmBundleToQuantity[usableBundle[ixBundle]]; 
        iRemaining -= (hmBundleToQuantity[usableBundle[ixBundle]] * usableBundle[ixBundle]); 
       } 

       //Right of current scope gets calculated 
       if (ixBundle > ixCursor) 
       { 
        hmBundleToQuantity[usableBundle[ixBundle]] += iRemaining/usableBundle[ixBundle]; 
        iRemaining = iRemaining % usableBundle[ixBundle]; 
       } 
      } 

      if (iRemaining == 0) return hmBundleToQuantity; 

      // Otherwise… We have nothing left on the stack we’ll check 
      // back to the beginning for non-zero values 
      int iNonEmptyStart = 0; 

      //Keep the current scope on the stack if the quantity is still bigger than zero 
      if (ixCursor >= 0 && hmBundleToQuantity[usableBundle[ixCursor]] > 0) 
      { 
       stBundleIndex.Push(ixCursor); 

       // Maximum cursor on the stack 
       // (this way we don’t decrement further back than we want) 
       iNonEmptyStart = stBundleIndex.Max(); 
      } 

      //Add last non-empty value to the stack to decrement and recalculate from there 
      for (int ixNonEmpty = usableBundle.Count - 1; ixNonEmpty >= iNonEmptyStart; ixNonEmpty--) 
      { 
       if (hmBundleToQuantity[usableBundle[ixNonEmpty]] > 0) 
       { 
        stBundleIndex.Push(ixNonEmpty); 
        break; 
       } 
      } 
     } 
     return null; 
    } 
} 

再次感謝！

Answer 2

這是一個有趣的問題來解決。極客指點四周。

我相信你的主要問題是試圖循環遍歷一個列表。真的，你想在這裏測試列表的所有變化，然後找到最高值的變化。

此外，正如在評論中所述，遞歸是你的朋友在這裏。我通過捆綁數量的每個排列遞歸。

你的數據存在的一個問題是你的例子。在這個例子中使用的數學是貪婪的。意思是，4在將餘數遞交給3之前將嘗試儘可能多地獲得它。4因此得到4個捆綁並且其餘1個返回空值。爲此，我認爲對17的正確答案應該是null。你可能能夠弄清楚如何在數字之間進行平衡，但這將是更多的邏輯IMO。

下面是代碼：

public class test 
{ 
    public static void Main() 
    { 
     var bundleSizes = new List<int> { 46, 25, 12, 4, 3 }; 

     var quantity = 30; 
     var bundleResults = Begin(bundleSizes, quantity); 
     Output(bundleSizes, quantity, bundleResults); 

     quantity = 17; 
     bundleResults = Begin(bundleSizes, quantity); 
     Output(bundleSizes, quantity, bundleResults); 

     quantity = 47; 
     bundleResults = Begin(bundleSizes, quantity); 
     Output(bundleSizes, quantity, bundleResults); 

     quantity = 5; 
     bundleResults = Begin(bundleSizes, quantity); 
     Output(bundleSizes, quantity, bundleResults); 

     Console.Read(); 
    } 

    static void Output(List<int> bundleSizes, int quantity, Dictionary<int, int> bundleResults) 
    { 
     var fullResults = new Dictionary<int, int>(); 
     bundleSizes.ForEach(
      delegate(int e) 
       { 
        var result = 0; 
        if(bundleResults != null) 
         bundleResults.TryGetValue(e, out result); 
        fullResults.Add(e, result); 
       }); 
     Console.WriteLine("Bundle Sizes: {0}", string.Join(",", bundleSizes)); 
     Console.WriteLine("Quantity: {0}", quantity); 
     Console.WriteLine("Returned Value: {0}", bundleResults == null ? "null" : fullResults.Aggregate("", (keyString, pair) => keyString + pair.Key + ":" + pair.Value + ",")); 
    } 

    static Dictionary<int, int> Begin(List<int> bundleSizes, int quantity) 
    { 
     var bundleCombinations = GetCombination(bundleSizes); 
     var tempBundleSizes = new List<Dictionary<int, int>>(); 
     foreach (var bundleCombination in bundleCombinations) 
     { 
      var tempBundleSize = new Dictionary<int, int>(); 
      bundleCombination.ForEach(e => tempBundleSize.Add(e, 0)); 
      var results = Bundle(bundleCombination, quantity); 
      if (results == null) 
       continue; 
      foreach (var result in results) 
      { 
       tempBundleSize[result.Key] = result.Value; 
      } 
      tempBundleSizes.Add(tempBundleSize); 
     } 
     var longest = tempBundleSizes.OrderByDescending(x => x.Count).FirstOrDefault(); 
     return longest; 
    } 

    static List<List<int>> GetCombination(List<int> list) 
    { 
     var retValue = new List<List<int>>(); 
     var count = Math.Pow(2, list.Count); 
     for (var i = 1; i <= count - 1; i++) 
     { 
      var retList = new List<int>(); 
      var str = Convert.ToString(i, 2).PadLeft(list.Count, '0'); 
      for (var j = 0; j < str.Length; j++) 
      { 
       if (str[j] == '1') 
       { 
        retList.Add(list[j]); 
       } 
      } 
      retValue.Add(retList); 
     } 
     return retValue; 
    } 

    static Dictionary<int, int> Bundle(List<int> bundleSizes, int quantity) 
    { 
     var bundleQuantities = new Dictionary<int, int>(); 
     bundleSizes.ForEach(delegate(int k) 
     { 
      if (k <= quantity) 
       bundleQuantities.Add(k, 0); 
     }); 
     return bundleQuantities.Count == 0 ? null : RecurseBundles(quantity, bundleQuantities.Keys.ToList(), bundleQuantities); 
    } 

    static Dictionary<int, int> RecurseBundles(int quantity, List<int> bundleSizes, Dictionary<int, int> bundleQuantities) 
    { 
     var bundleSize = bundleSizes.First(); 
     var bundles = (int)Math.Floor((double)quantity/bundleSize); 
     var remainingQuantity = quantity % bundleSize; 
     bundleQuantities[bundleSize] = bundles; 
     var remainingBundles = bundleSizes.Skip(1).ToList(); 
     if (!remainingBundles.Any() && remainingQuantity > 0) 
      bundleQuantities = null; 
     if (remainingBundles.Any()) 
      bundleQuantities = RecurseBundles(remainingQuantity, remainingBundles, bundleQuantities); 
     return bundleQuantities; 
    } 
} 

這裏是輸出：

Bundle Sizes: 46,25,12,4,3 
Quantity: 30 
Returned Value: 46:0,25:0,12:2,4:0,3:2, 
Bundle Sizes: 46,25,12,4,3 
Quantity: 17 
Returned Value: null 
Bundle Sizes: 46,25,12,4,3 
Quantity: 47 
Returned Value: 46:0,25:0,12:3,4:2,3:1, 
Bundle Sizes: 46,25,12,4,3 
Quantity: 5 
Returned Value: null 

特別感謝這些美妙的SO答案：

All Possible Combinations of a list of Values

How do I combine the keys and values of a Dictionary into one List using LINQ?

Find max count of a list of custom types

編輯：專爲在Output方法