c# - 号码分布

Question

我在分配号码以完全适合给定容器方面遇到问题。我的号码是:

int[] number = {50, 40, 30, 30, 25, 25};

我想找到一个最接近 100 的最佳组合，当没有更多可用选项时，开始另一个 100 的容器。像排序和从最大值到最小值相加这样的简单解决方案是行不通的，因为:

int[] firstContainer = { 50, 40 };         //10 unused
int[] secontContainer = { 30, 30, 25 };    //15 unused
int[] thirdContainer = { 25 };             //75 unused

我要找的结果是:

int[] firstContainer = { 50, 25, 25 };     //0 unused
int[] secontContainer = { 40, 30, 30 };    //0 unused

有好心人愿意帮我解决问题吗？

Answer 1

这是一个解决方案 - 它可以优化和改进，但现在您有了一个起点。起点是创建初始数组的所有组合，然后求和

static void Main(string[] args)
{
    int[] number = { 50, 40, 30, 30, 25, 25 };

    foreach (var kvp in Exercise(number, 100))
    {
        Console.WriteLine("Solution " + kvp.Key);
        foreach (var sol in kvp.Value)
        {
            Console.Write(sol + " ");
        }
        Console.WriteLine();
    }
}

private static Dictionary<int, List<int>> Exercise(int[] number, int sum)
{
    Dictionary<int, List<int>> results = new Dictionary<int, List<int>>();
    int counter = 0;

    var numberOfCombinations = Math.Pow(2, number.Count());
    for (int i = 0; i < numberOfCombinations; i++)
    {
        //convert an int to binary and pad it with 0, so I will get an array which is the same size of the input[] array. ie for example 00000, then 00001, .... 11111 
        var temp = Convert.ToString(i, 2).PadLeft(number.Count(), '0').ToArray();
        List<int> positions = new List<int>();
        int total = 0;
        for (int k = 0; k < temp.Length; k++)
        {
            if (temp[k] == '1')
            {
                total += number[k];
                positions.Add(number[k]);
            }
        }

        if (total == sum)
        {
            results.Add(counter, positions);
            counter++;
        }
    }

    return results;
}