今天在一个OFFICE大伽群里翻阅聊天记录,有群友说喜爱方方格子,因为它里面的凑数功能,自己写不出来,所以爱上现成的。
接着有老师再抛转出ExcelHome的经典老帖子香川裙子的凑数算法,大家都很认同确实经典。
在Excel催化剂第31波时,已经推出了凑数功能,当时也引用了香川老师的算法,因为不懂得怎么改C#的算法,索性带上了一个xlam文件,然后自定义函数时调用xlam文件里的VBA函数。
然后还有另外一个版本的凑数算法,使用的是google的一个规划求解库。但它底层是C++的封装,是区分64位和32位的。所以当时很别扭地把它变成一个web api放到服务端来调用。
当然今年在重构Excel催化剂的安装程序时,笔者也顺带改造了这个凑数功能,好奇心的驱动下,问了下chatGPT,得到了核心算法,效果非常出众。本来想写一篇推文介绍的,但后来忘记了,今天因为这个话题重新想起,就再写这篇推文了。
既然现阶段,向chatGPT要代码变得如此简单,想想,索性把代码开源给大家参考,想象力很重要,笔者想得到的效果,也是经过自己调整优化后得到的满意效果,兼顾性能和使用上的便利性。
实现了两个函数:CouShuWithGroup和CouShuWithGroupAll
CouShuWithGroup效果如下:返回一个N行3列的结果,分别是:分组组序号、分组值、凑数差异。
可以看到,Excel催化剂的版本,可以同时对一组待分组的数字集,一次性进行多个分组,每个数字只会归属一个组,并且给出了分组凑数后的差异,因为它只是尽可能地分组凑数,可能最后会有些尾差存在的。
CouShuWithGroupAll的效果如下:只对一个凑数值去运算,但返回多组满足条件结果,不过最好能限制不要返回太多组合数,太多组会有性能问题的,例如返回个10组已经够用了。
最新版的自定义函数,可以在Excel催化剂插件功能区左侧下拉更新。
或下载自定义安装程序也可以,不过WPS版本64位开始内测,如果安装64位的WPS,可能会有问题,未来再优化吧,下载地址:https://easyshu.lanzoue.com/iHIJq21wtp8d
最后,给大家公布源码的时候到了,有需要的可以自取。
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);
}
}
}
扫码关注腾讯云开发者
领取腾讯云代金券
Copyright © 2013 - 2025 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号:粤B2-20090059 深公网安备号 44030502008569
腾讯云计算(北京)有限责任公司 京ICP证150476号 | 京ICP备11018762号 | 京公网安备号11010802020287
Copyright © 2013 - 2025 Tencent Cloud.
All Rights Reserved. 腾讯云 版权所有