您好,欢迎访问三七文档
当前位置:首页 > 商业/管理/HR > 项目/工程管理 > 如何用EXCEL解决计算机背包问题
七步成诗:如何用EXCEL解决“背包问题”了解计算机的人都知道,背包问题是计算机较难解决的数学问题之一。所谓背包问题,是个形象的比喻:某人有个背包和已知数量的物品,背包只能装下限定的重量,每个物品重量不同。如何组合物品才能刚好装到背包指定的重量。(另外背包问题讨论的价值最大化,在这里暂不讨论。)该问题也可以是:财务人员要在一堆发票中,寻找到若干张发票加起来的值为一指定值。如果能快速解决此问题,将使工作效率大大提高。有些人说不就是随意拿几张发票,把金额加起来,多试几次不就行了?(专业术语回溯法)有些人说把所有发票金额可能性组合起来,每种组合先求解,选取正确的结果也是可以的吧?(专业术语递归法)此问题看似简单,其实不然。下面来举个小例子来分析其数学原理及难点:A公司向客户B公司开了九张发票并向申请收款,这九张发票金额分别为1521元、1314元、559元、2120元、5602元、498元、1120元、379元。客户由于资金问题只打来了6075元,由于客户相关人员出差联系上不,因此A公司财务只能靠自己来算:这6075元是哪几张发票之和?其数学原理很简单:把所有的发票进行排列组合,算出所有组合的结果。也就是求出一个数组的所有子集。此案例中有九张发票,每张发票在组合过程中存在两种状态:不将其组合和将其组合。这两种状态我们用0和1来表示。也就是说我们可以用二进制来表示,那么9张发票组合状态便是000000000-111111111的范围中。二进制的111111111等于十进制的511。也就是说财务人员可能最多要试算511次后才能得出结果。如果是十张发票呢?答案是1023次。如果是十一张发票呢?答案是2047次。如果是十六张发票呢?答案是65535次。这绝对是你想不到的工作量!网上有很多人在EXECL求助上提问此问题,但我没有发现正确答案。很多网友说可以用规划求解来解决这个问题。实践之后发现这个答案完全是在误人子弟。(规划求解是在特定的几个数字之间,而背包问题是不定数字)因此,我用了两天时间才思考出最单简的解决方法:(之前甚至想到用C语言或VBS编程来求解,但是由于感觉还是太麻烦就果断放弃了)下面我来说下如何用EXCEL来解决此问题。由于篇幅限制,我以四张发票为例。发票金额分别为13206、6542、7862、6321,另指定一个求合值27389作为我们的目标。具体算法如下表所示:第一步、列出所有的组合数量第二步、转换成二进制第三步、将4位二进制按位数填进对应的单元格中,我称之为栅格化第四步、填写发票金额第六步、求出每种组合的金额之和.第七步、就可以找出我们要的特定值了。123413206654278626321四张发票排列的上限是二进制1111(通过二制转十进制公式BIN2DEC,算出为十进制15),因此快速填充15行数。每一行代表一种组合。由于是四张发票,所以将二进制位数限定在四位,(若是九张发票,也要将二进制的位数改为9位)用到的公式:DEC2BIN(A4,4)用到的公式为=MID(数值,起始位,位数);例如:C4单元格中的公式。=MID($B4,C$2,1)第五步、将上面发票金额和对应的二进制数值栅格相乘。填在对应的格子里。这也就是所有金额的可能性组合10001000100063216321200100010007862078623001100110078626321141834010001000654200654250101010106542063211286360110011006542786201440470111011106542786263212072581000100013206000132069100110011320600632119527101010101013206078620210681110111011132060786263212738912110011001320665420019748131101110113206654206321260691411101110132066542786202761015111111111320665427862632133931分析并结论:一、以上方法算出结果仅需要两分钟,比编程还要快;二、EXCEL中,二进制最多只有9位,所以当超过9张发票时,进制转换的公式要改一下,具体如何改,我这里就不写了,因为百度上有很多答案。三、由于EXCEL最多只有65536行。因此一次性最多只能操作16位数字的组合。不过这很容易解决:如1..同一表格里做多列操作;2.分批次操作;2015年10月03日于上海浦东陈东昇QQ406828204
本文标题:如何用EXCEL解决计算机背包问题
链接地址:https://www.777doc.com/doc-5556021 .html