Алгоритм упаковки продуктов, при разных комбинациях?

Question

[manst]

Добрый день
У меня есть комбинации ид продуктов для упаковки, например [1,2] , [3,5] , [4,6,7], [4,8] и тд
Мне приходит заказ со списком продуктов [1,2,3,4,5,6,7,8,9,10]
Подскажите алгоритм упаковки для продуктов, что бы я в итоге получил:
[
[1,2],
[3,5],
[4,6,7],
[8],
[9],
[10]
]

Нужно также учитывать, что приоритет у комбинации в которую входит большее число продуктов. И надо стремится упаковать максимальное кол-во продуктов

Answer 1

[Даниил Басманов]

Это называется Задача о ранце или Knapsack problem. Советую начать с википедии, чтобы понять разные подтипы этой задачи, потом можете почитать примеры кода на Rosetta Code. Ещё могу предложить код из моего тулкита, он для чуть более простой задачи, вам придётся поменять алгоритм сравнения, если захотите его использовать.

spoiler

/// <summary>
/// Knapsack problem solver for items with equal value
/// </summary>
/// <typeparam name="T">Item identificator</typeparam>
/// <param name="set">
/// Set of items where key <typeparamref name="T"/> is item identificator and value is item weight</param>
/// <param name="capacity">Maximum weight</param>
/// <param name="knapsack">Pre-filled knapsack</param>
/// <returns>
/// Filled knapsack where values are number of items of type key.
/// Tends to overload knapsack: fills remainder with one smallest item.</returns>
/// <remarks>
/// https://en.wikipedia.org/wiki/Knapsack_problem
/// </remarks>
public static Dictionary<T, int> Knapsack<T>(Dictionary<T, float> set, float capacity,
    Dictionary<T, int> knapsack = null)
{
    var keys = new List<T>(set.Keys);
    // Sort keys by their weights in descending order
    keys.Sort((a, b) => -set[a].CompareTo(set[b]));

    if (knapsack == null)
    {
        knapsack = new Dictionary<T, int>();
        foreach (var key in keys)
        {
            knapsack[key] = 0;
        }
    }
    return Knapsack(set, keys, capacity, knapsack, 0);
}

private static Dictionary<T, int> Knapsack<T>(Dictionary<T, float> set, List<T> keys, float remainder,
    Dictionary<T, int> knapsack, int startIndex)
{
    T smallestKey = keys[keys.Count - 1];
    if (remainder < set[smallestKey])
    {
        knapsack[smallestKey] = 1;
        return knapsack;
    }
    // Cycle through items and try to put them in knapsack
    for (var i = startIndex; i < keys.Count; i++)
    {
        T key = keys[i];
        float weight = set[key];
        // Larger items won't fit, smaller items will fill as much space as they can
        knapsack[key] += (int) (remainder/weight);
        remainder %= weight;
    }
    if (remainder > 0)
    {
        // Throw out largest item and try again
        for (var i = 0; i < keys.Count; i++)
        {
            T key = keys[i];
            if (knapsack[key] != 0)
            {
                // Already tried every combination, return as is
                if (key.Equals(smallestKey))
                {
                    return knapsack;
                }
                knapsack[key]--;
                remainder += set[key];
                startIndex = i + 1;
                break;
            }
        }
        knapsack = Knapsack(set, keys, remainder, knapsack, startIndex);
    }
    return knapsack;
}

Comments

[Wataru]

Больше похоже на Set Cover.

[manst]

Спасибо, почитаю