Algorithm for packaging products, with different combinations?

Question

Algorithms

Good afternoon
I have a combination of product ids for packaging, for example [1,2] , [3,5] , [4,6,7], [4,8] and so on.
I receive an order with a list of products [1,2, 3,4,5,6,7,8,9,10]
Tell me the packing algorithm for products, what would I get in the end:
[
[1,2],
[3,5],
[4,6,7],
[8],
[9],
[10]
]
It should also be taken into account that the combination that includes a larger number of products has priority. And we must strive to pack the maximum number of products

Answer 1

This is called the Knapsack problem or the Knapsack problem . I advise you to start with wikipedia to understand the different subtypes of this task, then you can read the code examples on Rosetta Code . I can also offer code from my toolkit, it is for a slightly simpler task, you will have to change the comparison algorithm if you want to use it.

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