『凑数功能巅峰之作』新版本的凑数功能，由chatGPT辅助完成（源码公开）

using ExcelDna.Integration;
using System;
using System.Collections.Generic;
using System.Linq;
using MoreLinq;

namespace ExcelCuiHuaJi
{
    public partial class ExcelUDF
    {
        [ExcelFunction(Category = "规划求解类", Description = "分组凑数，从源数据列中，抽取出指定的项目组合，使其求和数最大限度接近分组的大小。Excel催化剂出品，必属精品！")]
        public static object CouShuWithGroupAll(
                                                  [ExcelArgument(Description = "需要凑数的原始数据单元格区域，精度最好不走过4位小数点，多于4位可能会出现精度问题影响准确度")] object[] srcRange,
                                                  [ExcelArgument(Description = "要凑数求和的目标值")] double targetValue,
                                                   [ExcelArgument(Description = "满足凑数目标值的最大组合数，如果满足的组全太多，会非常慢，尽可能设置不要太多组合数返回")] int maxGroupCount
                                                   )
        {
            maxGroupCount = maxGroupCount == 0 ? 99 : maxGroupCount;
            var srcValues = srcRange.Select(s => Convert.ToDecimal(s)).ToArray();

            var scale = DetermineScale(srcValues);
            var values = srcValues.Select(s => Convert.ToInt32(s * scale)).ToArray();
            var target = Convert.ToInt32(targetValue * scale);
            var resultOfKnapsack = KnapsackAll(values, target, maxGroupCount);
            var rowsCount = resultOfKnapsack.SelectMany(s => s).Count();
            var arr = new object[rowsCount, 2];
            int iloop = 0;
            for (int i = 0; i < resultOfKnapsack.Count; i++)
            {
                var currentGroupValues = resultOfKnapsack[i];

                for (int j = 0; j < currentGroupValues.Count; j++)
                {
                    arr[iloop + j, 0] = i + 1;
                    arr[iloop + j, 1] = currentGroupValues[j];
                }

                iloop = iloop + currentGroupValues.Count;
            }

            return arr;
        }


        [ExcelFunction(Category = "规划求解类", Description = "分组凑数，从源数据列中，抽取出指定的项目组合，使其求和数最大限度接近分组的大小。Excel催化剂出品，必属精品！")]
        public static object CouShuWithGroup(
                                                   [ExcelArgument(Description = "需要凑数分组的原始数据单元格区域，精度最好不走过4位小数点，多于4位可能会出现精度问题影响准确度")] object[] srcRange,
                                                   [ExcelArgument(Description = "限定组的凑数目标值上限的单元格区域，可选多个单元格代表分多个组，组的大小可不相同，尽量较难组合的放最上面优先对其组合")] object[] groupeRange
                                                    )


        {
            var srcValues = srcRange.Select(s => Convert.ToDecimal(s)).ToArray();

            var scale = DetermineScale(srcValues);
            var values = srcValues.Select(s => Convert.ToInt32(s * scale)).ToList();
            var capacitys = groupeRange.Select(s => Convert.ToInt32((double)s * scale)).ToArray();
            var arrResult = new object[values.Count, 3];
            var list = new List<(int Index, int GroupIndex, int GroupValue, int MaxValue)>();

            var dicIndexMapping = new Dictionary<int, int>();
            for (int i = 0; i < capacitys.Length; i++)
            {
                var matchValueWithIndexes = values.Index(0).Where(s => list.All(t => t.Index != s.Key)).ToList();
                dicIndexMapping = matchValueWithIndexes.Index(0).ToDictionary(k => k.Key, v => v.Value.Key);
                var newValues = matchValueWithIndexes.Select(s => s.Value).ToList();

                var capacity = capacitys[i];
                var result = ZeroOneKnapsack(newValues, newValues, capacity);

                if (dicIndexMapping.Count == 0)
                {
                    foreach (var itemIndex in result.ItemIndexes)
                    {
                        list.Add((itemIndex, i, capacity, result.MaxValue));
                    }
                }
                else
                {
                    foreach (var itemIndex in result.ItemIndexes)
                    {
                        var index = dicIndexMapping[itemIndex];
                        list.Add((index, i, capacity, result.MaxValue));
                    }
                }


            }


            for (int i = 0; i < arrResult.GetLength(0); i++)
            {
                var matchItem = list.FirstOrDefault(s => s.Index == i);
                if (matchItem.MaxValue == 0) //返回的结果为空，元组为默认值，整形为0
                {
                    //这里是没有命中，剩余多出来的记录,变成假空，最终返回Excel时，才不会用0来填充。
                    arrResult[i, 0] = "";
                    arrResult[i, 1] = "";
                    arrResult[i, 2] = "";
                }
                else
                {
                    arrResult[i, 0] = matchItem.GroupIndex + 1;
                    arrResult[i, 1] = matchItem.GroupValue * 1.0 / scale;
                    arrResult[i, 2] = (matchItem.GroupValue - matchItem.MaxValue) * 1.0 / scale;
                }

            }

            return arrResult;
        }


        private static (int MaxValue, List<int> ItemIndexes) ZeroOneKnapsack(List<int> values, List<int> weights, int capacity)
        {
            int n = values.Count;
            int[,] dp = new int[n + 1, capacity + 1];
            bool[,] itemIncluded = new bool[n, capacity + 1];

            // 构建动态规划表
            for (int i = 1; i <= n; i++)
            {
                for (int w = 1; w <= capacity; w++)
                {
                    if (weights[i - 1] <= w)
                    {
                        if (values[i - 1] + dp[i - 1, w - weights[i - 1]] > dp[i - 1, w])
                        {
                            dp[i, w] = values[i - 1] + dp[i - 1, w - weights[i - 1]];
                            itemIncluded[i - 1, w] = true;
                        }
                        else
                        {
                            dp[i, w] = dp[i - 1, w];
                        }
                    }
                    else
                    {
                        dp[i, w] = dp[i - 1, w];
                    }
                }
            }

            // 回溯找到物品组合
            List<int> items = new List<int>();
            int remainingCapacity = capacity;
            for (int i = n - 1; i >= 0; i--)
            {
                if (itemIncluded[i, remainingCapacity])
                {
                    items.Add(i);
                    remainingCapacity -= weights[i];
                }
            }

            return (dp[n, capacity], items);
        }

        private static List<List<int>> KnapsackAll(int[] values, int target, int maxGroupCount)
        {
            var allCombinations = new List<List<int>>();
            var currentCombination = new List<int>();
            FindCombinations(values, target, 0, currentCombination, allCombinations, maxGroupCount);
            return allCombinations;
        }

        static void FindCombinations(int[] values, int target, int index, List<int> currentCombination, List<List<int>> allCombinations, int maxGroupCount)
        {
            if (allCombinations.Count == maxGroupCount)
            {
                return;
            }

            if (target == 0)
            {
                allCombinations.Add(new List<int>(currentCombination));
                return;
            }

            for (int i = index; i < values.Length; i++)
            {
                if (values[i] <= target)
                {
                    currentCombination.Add(values[i]);
                    FindCombinations(values, target - values[i], i + 1, currentCombination, allCombinations, maxGroupCount);
                    currentCombination.RemoveAt(currentCombination.Count - 1);
                }
            }
        }

        public static int DetermineScale(decimal[] numbers)
        {
            int maxDecimalPlaces = 0;
            foreach (var number in numbers)
            {
                int decimalPlaces = BitConverter.GetBytes(decimal.GetBits(number)[3])[2];
                if (decimalPlaces > maxDecimalPlaces)
                {
                    maxDecimalPlaces = decimalPlaces;
                }
            }
            return (int)Math.Pow(10, maxDecimalPlaces);
        }
    }
}