已知集合下一定个数的数字之和得到指定数字

码拜

9年 ago

已知一个集合 int[] data = new int[]{100,50,30,20,10,5};要求从这里面取数字，允许重复，在不超过指定个数下，算出最小的和为指定值或比指定值大但最接近的列表，相等优先，最小值优先。
例如100，要求5，有50= 50或 50= 30 +20或 50= 5+5+5+5+30，此时应该选最后一种，就是最小的值用的越多越好。假如是49，怎么算都得不到49，就取能算得到比它大的最接近的数，也就是50，所以49 = 5+5+5+5+30。
求高手帮忙

解决方案

查下打包算法，但跟你的有点差异，原因是打包是不允许超出上限的

全部的数学规划都是需要检查全部可能的组合的，当然你可以在达成某个条件时，让枚举提前结束
然后说：这个算法可以得到可能的解，但不一定是最优解
本人不是学生，所以也没有必要按书本上的套路来。

        static void Main(string[] args)
        {
            int[] data = { 100, 50, 30, 20, 10, 5 };
            int total = 42;
            int n = 5;
            Array.Sort(data); //升序排列
            int min = data[0];
            foreach (var x in Descartes(data, n))
            {
                var t = x.Sum() - total;
                if(t == 0 || (t > 0 && t < min)) Console.WriteLine(string.Join(",", x));
            }
        }
        static IEnumerable<IEnumerable<int>> Descartes(int[] data, int num)
        {
            foreach (int x in data)
            {
                var r = new int[] { x };
                if (num == 1) yield return r;
                else
                {
                    foreach (var y in Descartes(data, num - 1))
                    {
                        if(x <= y.ToArray()[0]) yield return r.Concat(y);
                    }
                }
            }
        }