利用背包算法解决分组凑数问题

香川群子 · 发表于 2017-7-25 20:33

lzqlaj 发表于 2017-7-25 17:35
《数论》里的多元一次方程的求解问题。

不是多元一次方程问题。

多元一次方程的整数解，另有递归算法可解。

学不完用不尽 · 发表于 2017-7-25 21:43

观摩观摩。。。

三坛老窖 · 发表于 2017-7-26 01:15

香川群子发表于 2017-7-24 23:04
似乎也可以用来解决一维下料问题……

但是目前是手工确定选用合适规格，应该要能自动化才算实用。

对于一维下料问题，利用动态规划原理求取当前的最优切割方式，然后组成整体下料方案，其实质就是分层+贪婪。在最初接触这个问题时我就试过，效果不理想。此路似乎行不通。
动态规划原理用于凑数，倒是不错的，应能生成性能优于你【 2014新年元旦第一强帖：实用凑数凑金额高效递归剪枝算法】的程序。我看你想试，怎么半途而废了呢？

lyb200 · 发表于 2017-7-26 08:06

收藏一下。。。以后看。

香川群子 · 发表于 2017-7-26 17:30

三坛老窖发表于 2017-7-26 01:15
对于一维下料问题，利用动态规划原理求取当前的最优切割方式，然后组成整体下料方案，其实质就是分层+贪 ...

我早就试过了，背包算法的最大困难是只能处理整数，如果总和较大，就需要定义一个开销很大内存的数组，

这是很不现实的。

所以，这个只能计算小学水平的凑数。

如下面帖子的几个简单数字，用背包算法就算不下去了。
http://club.excelhome.net/forum. ... 161&pid=9177232

today0427 · 发表于 2017-7-26 17:39

小学水平这个适合我，好好学习下！向老师致敬！

三坛老窖 · 发表于 2017-7-26 18:31

本帖最后由三坛老窖于 2017-7-26 20:38 编辑

香川群子发表于 2017-7-26 17:30
我早就试过了，背包算法的最大困难是只能处理整数，如果总和较大，就需要定义一个开销很大内存的数组，
...

你所列链接中的问题与下面链接中的问题几乎完全一样。
http://club.excelhome.net/forum.php?mod=viewthread&tid=1337931
将你所列链接中问题的数据转为整数，或将代码中定义的和值数据类型改为货币型，可瞬间秒杀。
附件中所用的就是动态规划原理+内置字典，若是大数据，则可用该原理+数组来解决。

香川群子 · 发表于 2017-7-29 10:54

三坛老窖发表于 2017-7-26 18:31
你所列链接中的问题与下面链接中的问题几乎完全一样。
http://club.excelhome.net/forum.php?mod=viewth ...

研究了你链接中的代码，结果大失所望。

用了最原始的全组合算法。效率最低，所以完全没有意义，哈哈。

suxianchun1 · 发表于 2017-7-30 09:20

香川算法太厉害了，我有个问题想问下，剪枝算法，有个疑问，如果按照日期靠前的优先获取出金额组合怎么改

suxianchun1 · 发表于 2017-7-30 09:24

大神，我的问题我在这里阐述下，能否帮忙解决下，就是客户给定一些金额，金额大小不固定，按照日期排序，从一些金额里筛选出组合近似制定金额的组合，但是需要按照日期排序筛选，请问怎么解决

		自动登录	找回密码
密码			免费注册

[分享] 利用背包算法解决分组凑数问题

评分