动态规划算法在管理会计中的应用钟方源-一、应用动态规划算法的动机案例1：一家公司现有m万元，本年可投资的业务有n项。其中，第一项业务对应的成本是C1，收益是R1；第二项业务对应的成本是C2，收益是R2……第n项业务对应的成本是Cn，收益是Rn。假设同种业务只能投资一次，不可重复。若每项业务对应的成本和收益已知，求该公司用m万元投资这些业务可以取得的最大收益。显然可以用递归法来解决此问题：设V（i，j）表示能够用j万元购买的前i项业务收益最大的子集的收益。根据V（i，j）这个最佳子集中是否包含业务i，可以得到下列递归关系式：V（i，j）=该方程表示的是：如果第i项业务的成本Ci比j小（或等于j），那么取得最大收益的方案有可能包含该项业务，至于是否包含，就看包含该业务所能取得的最大收益与不含该业务所能取得的最大收益两者中何者更大。而如果第i项业务的成本Ci比j大，那就不能选择购买该项业务，也就是说取得最大收益的方案一定不包含此项业务。当i和j有至少一项等于零时，表示该公司投资业务的资金为零或者不投资任何业务，所以其所能取得的收益一定为零，即当i=0或j=0时，V（i，j）=0，故该方程的边界条件是：该案例目标是求出V（n，m），即用m万元购买的n项业务收益最大的子集的收益。因此，可以得到以下递归过程（伪代码）：functionV（i，j：integer）；beginif（i=0）or（j=0）thenreturn0elsebeginifj-Ci>=0thenAnswer：=max［V（i-1，j），Ri+V（i-1，j-Ci）］；ifj-Ci<0thenAnswer：=V（i-1，j）；end；end；1.记忆化搜索。上面的递归算法显然是正确的，但是它的运算速度却很慢，因为它的时间复杂度是指数级的。如果记V（i，j）的值是d［i，j］，以数组来表示，由于1≤i≤n，1≤j≤m，所以一共只有O（n×m）个d值需要计算，而在执行递归算法的时候却做了大量的重复运算。可以这样改进这个算法：因为V（i，j）的值一旦被计算出来就不会改变，所以在每次调用V函数之前先检查之前是否已经计算过该值，如果是，则直接从数组中读出，不必再花费时间重新进行计算，即：functionV（i，j：integer）；beginifCalculated［i，j］thenreturnd［i，j］；//此处为原来的V函数代码d［i，j］：=Answer；Calculated［i，j］：=true；end；2.自底向上的递推。除了上述这种改进方法，还有另外一种改进方法：可以按照一定的顺序计算所有的d值。由于计算d［i，j］需要知道d［i-1，j］和d［i-1，j-Ci］，所以可以按照i~j递增的顺序来计算d［i，j］，即：动态规划算法在管理会计中的应用【摘要】动态规划算法是运用状态转移解决多阶段决策的一种最优化方法。这种方法基于最优化原理，把多阶段过程转化为一系列单阶段问题，进而逐个求解，可以高效地解决许多用贪心算法或分治算法无法解决的问题。本文结合管理会计中的问题，运用运筹学、金融建模等知识，探讨了动态规划算法在管理会计中的应用。【关键词】动态规划；管理会计；最优化原理【】F230【文献标识码】A【】1004-0994（2016）05-0053-3钟方源max｛V（i-1，j），Ri+V（i-1，j-Ci）｝，j-Ci≥0V（i-1，j），j-Ci<0V（0，j）=0，j≥0V（i，0）=0，i≥02016.05财会月刊·53·□财务·会计□下载文档原格式(PDF原格式，共3页)付费下载一、应用动态规划算法的动机案例1：一家公司现有m万元，本年可投资的业务有n项。其中，第一项业务对应的成本是C1，收益是R1；第二项业务对应的成本是C2，收益是R2……第n项业务对应的成本是Cn，收益是Rn。假设同种业务只能投资一次，不可重复。若每项业务对应的成本和收益已知，求该公司用m万元投资这些业务可以取得的最大收益。显然可以用递归法来解决此问题：设V（i，j）表示能够用j万元购买的前i项业务收益最大的子集的收益。根据V（i，j）这个最佳子集中是否包含业务i，可以得到下列递归关系式：V（i，j）=该方程表示的是：如果第i项业务的成本Ci比j小（或等于j），那么取得最大收益的方案有可能包含该项业务，至于是否包含，就看包含该业务所能取得的最大收益与不含该业务所能取得的最大收益两者中何者更大。而如果第i项业务的成本Ci比j大，那就不能选择购买该项业务，也就是说取得最...