银行有一台ATM机。对于特定的一周，以百万计的现金使用情况如下。
- 5-周一
- 4-周二
- 1-周三
- 15-周四
- 6-周五
- 2-周六
- 4-周日
银行聘请一家存款公司每周进行5轮、3轮或1轮存款。
存款公司在收取存款费用时向银行提供以下套餐，
-
每月4轮存款的成本-21135
-
每月12轮存款的成本-32000
-
每月20轮存款的成本-41975
订单保持为周一、周二、周三、周四、周五、周六、周日。对值进行分类时不应违反此顺序。
示例
- 5轮
[(5+4)，1，15，6，(2+4)]
[(5+4)，1，(15+6)=20+1,2,4]
可以有许多其他不会破坏秩序的组合。
- 3轮
[(5+4+1)，15，(6+2+4)]
[(5+4)，(1+15)，(6+2+4)]
可以有许多其他不会破坏秩序的组合。
- 1轮
[(5+4+1+15+6+2+4)]
此外，银行还必须承担当天结束时剩余金额的0.019%的持有成本。
示例
考虑第一周的现金使用情况如下。(单位：百万)
星期一-13
周二-5
星期三-4
周四-4
周五-2
周六-11
Sun-1
5轮
第一周现金存款订单-13，(5+4)，4，(2+11)，1
假设存款在一个月的所有4周内分5轮完成，(5*4=20)
总存款成本=41975
沉积了1-13个，13退出，剩余0，0持有成本
2-(5+4)沉积，5个退出，剩余4个，4*0.00019持有成本
沉积了3-0，4个退出，剩余0，0持有成本
4-4沉积，4个退出，剩余0，0持有成本
5-(2+11)沉积，2退出，剩余11个，11*0.00019持有成本
沉积6-0，11退出，剩余0，0持有成本
沉积了7-1，1撤回，剩余0，0持有成本
第一周的总持有成本=4*0.00019+1*0.00019=0.00285百万=2850
同样，我需要找到考虑到每一周的当月总持有成本。
3轮
第一周现金存款订单-13，(5+4+4)，(2+11+1)=(1+1+12)
编辑-假设每月选择12轮套餐，因此每周3轮(3*4=12)
总存款成本=32000
沉积了1-13个，13退出，0剩余，0持有成本
2-(5+4+4)存入，5提取，(4+4)剩余，(4+四)*0.00019持有成本
3-0存入，4取出，4剩余，4*0.00019持有成本
4-0存入，4提取，0剩余，0持有成本
5-(2+11+1)存入，2取出，(11+1)剩余，(11+1*)*0.00019持有成本
6-0存入，11取出，1剩余，1*0.00019持有成本
7-0存入，1提取，0剩余，0持有成本
第一周的总持有成本=(4+4)*0.00019+4*0.00019+(11+1)*0.00019+1*0.00019=0.00475百万=4750
同样，我需要找到考虑每周的当月总持有成本。
编辑-假设41975包已被选中。这意味着每月存入20轮现金。这意味着每周5轮。如果选择了32000个包裹，那么每月12轮。这意味着每周3轮。如果选择21135包，则意味着每月4轮，即每周1轮。在特定月份的四周内，不存在5,3,1的混合组合。只有所有四周都是在1、3或5轮中完成的。我们必须考虑持有成本和包装成本来选择最佳包装。
5轮的好组合不会违反顺序，可以比所有3轮解决方案和1轮解决方案更好。同样适用于三轮解决方案。否则，1轮解决方案可能比所有5轮和3轮解决方案更好。
当存款轮次增加时，持有成本降低，但存款成本增加。当轮次减少时，存款成本降低，但持有成本增加。因此，我需要找到一个月中每周的存款顺序和每月的存款包，它可以在总持有成本和总存款成本之间做出很好的权衡，消耗最少的时间。
对该方法的任何见解都将非常有帮助。
在您的情况下，对于每种套餐选择，您都有一个固定月度成本(FMC)和一个可变月度成本(VMC)FMC在{x，x+10000，x+20000}中，而VMCstrong>VWC每周可变成本的总和VWC由一组天数D=(M，T，W，T，F，S，S)的区间划分为k个不相交的子区间来确定，其中k在{1,3,5}中。
因此，您必须选择最小值｛FMC1+VMC1*、FMC3、FMC5+VMC5*｝，其中VMCk表示将D划分为k个间隔的最小可变月度成本(请注意，对于k=1的情况，答案很简单，因为每周都有一个分区)。由于可变每周成本为VWC=0.7*(r1+r2+r3+r4+r5+r6+r7)，ri是i一天的剩余量，因此这一切都可以归结为最小化每周的剩余量。在计算VMCk*时，您可以使用本文中描述的DP算法，目的是最大限度地减少每周的剩余量。
所以在高级：
- 对于每包存款｛1,3,5｝，使用DP获得每周的最小可变成本->最小剩余金额。然后将可变的每月成本作为4周的总和
- 从考虑每个包装的固定成本和在1中获得的可变成本中选择最小总成本