c# - 同じ重み/値を持つ修正されたナップサック/サブセット合計

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
- 戻り値: null

この問題をどうするか。

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

score 2 · Accepted Answer

これは解決するのが楽しい問題でした。いたるところにオタクポイント。

私が信じるあなたの主な問題は、単一のリストをループしようとすることです。ここで実際に必要なのは、リストのすべてのバリエーションをテストしてから、最も高い値を持つものを見つけることです。

また、コメントに記載されているように、ここでは再帰があなたの友達です。バンドル金額の各順列を繰り返しました。

あなたのデータが抱えている問題の1つは、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 を使用してディクショナリのキーと値を 1 つのリストに結合するにはどうすればよいですか?

カスタムタイプのリストの最大数を見つける

Output編集:メソッドでより適切にフォーマットされた出力のために小さな変更を加えました

score 1 · Accepted Answer

ソリューションにさらに取り組み、同僚とpaqogomezの回答のおかげで、私のすべての例などで機能する正しいコードを取得しました! 私の同僚は、再帰の代わりにスタックを使用し、そのスタックを使用して、バンドルリストの左右にあるインデックスを追跡できることを教えてくれました。このコードは、Greedy Brute-force ソリューションを使用しています。より高速な方法があれば、興味があります。

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 に特に感謝します!

c# - 同じ重み/値を持つ修正されたナップサック/サブセット合計

2 に答える 2

Related

Reference