2014新年元旦第一强帖：实用凑数凑金额高效递归剪枝算法

我的一生14

学习一下，谢谢香川老师

ghostjiao

香川老师你好：
我现在遇到另外一种凑数情况，麻烦指导一下，如图所示。把100分给这几个地区，怎么样分配能使分配之后，每个地区的数量除以指导线这个值 几个区最接近。
数量都是整数，或者说是我们可以设定一个误差值，比如让最终除以的结果，几个区的误差值在5%以内。不考虑数据本来不合理，根本就不能够达到误差5%以内。
或者其他任何方法，自己没有思路，不一定是我说的这样，就类似于这种求最优解的问题，麻烦香川老师给点指导，多谢！

香川群子

ghostjiao 发表于 2014-7-22 21:28
香川老师你好：
我现在遇到另外一种凑数情况，麻烦指导一下，如图所示。把100分给这几个地区，怎么样分配能 ...

你这个根本就是小学生问题：

指导线总和=150，因此分配权重=100/150=2/3
然后每个地区按=Round([指导线]*[权重],0) 四舍五入计算、最后个别调整一下即可。

ghostjiao

香川群子 发表于 2014-7-23 08:56
你这个根本就是小学生问题：

指导线总和=150，因此分配权重=100/150=2/3

...这个，实际上要复杂点，我想想换个模拟方法，多谢！

香川群子

ghostjiao 发表于 2014-7-23 09:17
...这个，实际上要复杂点，我想想换个模拟方法，多谢！

那就老老实实地把实际问题提出来……

模拟也许能说明问题，但也可能无法替代实际，反而让别人误入歧途。

Kelidai

学习了，太强大了。

香川群子

Kelidai 发表于 2014-8-17 13:05
学习了，太强大了。

我这帖子发了大半年了……你咋才来呀？ 你还是不是香川粉？！

barry1126

工作中碰到的事情：我是超市的一名出纳，工作中经常有人来买购物卡，人家说开办公用品1025元，我要给人家附个明细，现在都是手工凑单太累，所以才有了这个想法，请大师帮忙，谢谢！ 复件 发票清单.rar (22.86 KB, 下载次数: 40)

2014-9-8 21:40 上传

点击文件名下载附件

香川群子

barry1126 发表于 2014-9-8 21:41
工作中碰到的事情：我是超市的一名出纳，工作中经常有人来买购物卡，人家说开办公用品1025元，我要给人家附 ...

你的问题很实际，但也不太容易。

因为数据种类比较多，所以任意一个金额的有效组合都有成千上万种，这反而造成问题。


所以，你必须明确规则：
1. 是否规格个数有限制？
比如，我只用2种规格就能凑出1025元，行不行？

2. 如果规格是否有优先权？
比如，某些规格尽量含有

3. 所配个数是否有数量限制？或者任意？


…………
为简化计算，建议：
一、是否可以先生成一些基本模板，如 500元、750元、1000元……
然后在此基础上适当增减调整。

这样，凑数要求就只是25元、132元这样较小的范围了。

呵呵。

barry1126

香川群子 发表于 2014-9-9 09:02
你的问题很实际，但也不太容易。

因为数据种类比较多，所以任意一个金额的有效组合都有成千上万种，这 ...

谢谢大师！
我把最原始的表格再发给你，原来只有品名、单价、单位，根据这些进行凑单。 复件 发票清单1.zip (15.84 KB, 下载次数: 33)

2014-9-9 10:14 上传

点击文件名下载附件

你说的几个问题：
1、关于个数。原则是钱少条目相对就少，钱多相对就多。如果1000元有四五个条目也就够了，如果是500元三个条目也够了，如果是10000元的话，可以上升到十个或者十五个条目。
2、关于规格是否有优先权的问题。我的想法是点一下凑单出一种结果，觉得不满意，再点一次如果可能再出一次结果。不知能否实现。
3、所配个数，跟第一条一样。
4、关于预先生成的基本模板问题。条目、个数都是固定的，我怕老板说为什么每都是这几个，尽量有所差别

在这里再次谢谢楼主。