CODEWITHSUNDEEP
c#algorithmsorting
Robert Hyndman
Robert Hyndman

Reputation: 13

Consuming a number into descending groups

I always struggle with these types of algorithms. I have a scenario where I have a cubic value for freight and need to split this value into cartons of different sizes, there are 3 sizes available in this instance, 0.12m3, 0.09m3 and 0.05m3. A few examples;

Assume total m3 is 0.16m3, I need to consume this value into the appropriate cartons. I will have 1 carton of 0.12m3, this leave 0.04m3 to consume. This fits into the 0.05m3 so therefore I will have 1 carton of 0.05m, consumption is now complete. Final answer is 1 x 0.12m3 and 1 x 0.05m3.

Assume total m3 is 0.32m3, I would end up with 2 x 0.12m3 and 1 x 0.09m3.

I would prefer something either in c# or SQL that would easily return to me the results.

Many thanks for any help.

Cheers

Upvotes: 1

Views: 84

Answers (1)

Sach
Sach

Reputation: 10393

I wrote an algorithm that may be a little messy but I do think it works. Your problem statement isn't 100% unambiguous, so this solution is assuming you want to pick containers so that you minimize the remaining space, when started filling from the largest container.

// List of cartons
var cartons = new List<double>
{
    0.12,
    0.09,
    0.05
};

// Amount of stuff that you want to put into cartons
var stuff = 0.32;

var distribution = new Dictionary<double, int>();

// For this algorithm, I want to sort by descending first.
cartons = cartons.OrderByDescending(x => x).ToList();

foreach (var carton in cartons)
{
    var count = 0;
    while (stuff >= 0)
    {
        if (stuff >= carton)
        {
            // If the amount of stuff bigger than the carton size, we use carton size, then update stuff
            count++;
            stuff = stuff - carton;
            distribution.CreateNewOrUpdateExisting(carton, 1);
        }
        else
        {
            // Otherwise, among remaining cartons we pick the ones that will have empty space if the remaining stuff is put in
            var partial = cartons.Where(x => x - stuff >= 0 && x != carton);
            if (partial != null && partial.Count() > 0)
            {
                var min = partial.Min();
                if (min > 0)
                {
                    distribution.CreateNewOrUpdateExisting(min, 1);
                    stuff = stuff - min;
                }
            }
            else
            {
                break;
            }
        }
    }

There' an accompanying extension method, which either adds an item to a dictionary, or if the Key exists, then increments the Value.

public static class DictionaryExtensions
{
    public static void CreateNewOrUpdateExisting(this IDictionary<double, int> map, double key, int value)
    {
        if (map.ContainsKey(key))
        {
            map[key]++;
        }
        else
        {
            map.Add(key, value);
        }
    }
}

EDIT

Found a bug in the case where initial stuff is smaller than the largest container, so code updated to fix it.

NOTE

This may still not be a 100% foolproof algorithm as I haven't tested extensively. But it should give you an idea on how to proceed.

EDIT EDIT

Changing the condition to while (stuff > 0) should fix the bug mentioned in the comments.

Upvotes: 1

Related Questions