Модифицированный ранец/сумма подмножества с тем же весом/значениями

Это была забавная проблема, которую нужно было решить. Компьютерщик указывает все вокруг.

Я считаю, что ваша главная проблема заключается в попытке просмотреть один список. На самом деле вам нужно проверить все варианты списка, а затем найти вариант с самыми высокими значениями.

Кроме того, как указано в комментариях, рекурсия здесь ваш друг. Я повторил каждую перестановку сумм пакетов.

Одна проблема, которая есть у ваших данных, связана с вашим 17 примером. Математика, используемая в этом примере, является жадной. Это означает, что 4 попытается получить как можно больше, прежде чем передать остаток 3. Таким образом, 4 получает 4 пакета, а с 1 остатком возвращается ноль. По этой причине я думаю, что правильный ответ на 17 должен быть null. Возможно, вы сможете понять, как балансировать между числами, но это будет намного больше логики, ИМО.

Вот код:

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

Больше поработал над решением, и благодаря коллеге и ответу paqogomez мы получили правильный код, который работает для всех моих примеров и не только! Мой коллега показал мне, что вы можете использовать стек вместо рекурсии и использовать стек для отслеживания индекса, который смотрит слева и справа от списка пакетов. Этот код использует решение Greedy Brute-force, если есть более быстрый способ, мне будет интересно!

Код С#:

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 за некоторую помощь в решении!