4

我正在研究一个必须处理背包/子集和问题的特殊情况的问题。问题如下：

您有一组随机递减的捆绑包大小，例如：{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;
    }
}
4

2 回答 2

2

这是一个有趣的问题要解决。到处都是极客点。

我认为您的主要问题是尝试遍历单个列表。您真正想要的是测试列表的所有变体，然后找到具有最高值的变体。

此外，正如评论中所述，递归是您的朋友。我通过捆绑数量的每个排列进行递归。

您的数据存在的一个问题是您的 17 个示例。这个例子中使用的数学是贪心的。意思是，4 将在将剩余部分交给 3 之前尝试尽可能多地获取。因此，4 得到 4 个捆绑包，剩余 1 个则返回 null。出于这个原因，我认为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 答案：

值列表的所有可能组合

如何使用 LINQ 将字典的键和值组合到一个列表中？

查找自定义类型列表的最大计数

Output编辑：为方法中更好的格式化输出进行了小改动

于 2013-11-21T07:42:20.463 回答
1

在解决方案上进行了更多工作，感谢同事和 paqogomez 的回答，我们得到了适用于我所有示例的正确代码等等！我的同事向我展示了您可以使用堆栈代替递归，并使用堆栈来跟踪查看捆绑列表左侧和右侧的索引。这段代码使用了贪婪的蛮力解决方案，如果有更快的方法我会感兴趣！

C#代码：

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;
    }
}

再次感谢为此提供的所有帮助，并特别感谢我的同事和 paqogomez 对解决方案的帮助！

于 2013-12-02T19:46:55.380 回答