修改决策后 不太明白为什么能满足最优子结构

Question

老师您好 这一点还是没有想清楚：
在修改决策为 “第K周要交付的机器应该在第几周生产”后，验证最优子结构时，有点疑问。

假设只看K周，第K周的机器交给第i周生产，第i周的总成本会增加一些，如果有了第k+1周时，k+1周的机器也交给第i周生产，那么第i周总成本就会再增加一些，因此在生产时长为k周和生产时长k+1周情况下，第i周的总生产成本就不相同了，岂不是没有满足最优子结构？

Answer 1

吉他熊 2023-02-11 17:05:50

同学你好！

首先，最优子结构的含义，是“当前阶段的问题的最优解，一定是从前面阶段的问题的最优解得出”，也就是说，前面阶段的非最优解，一定不会导致当前阶段的最优解，这也是为什么我们需要分阶段求最优解

然后，我们对子问题的定义是“完成前K周订单的总成本”，这个总成本只包含“完成前K周的订单”，而不考虑这周给后续其他周生产所导致的成本。

比方说你举的例子，对于第i周，我们计算的时候只考虑第1~i周需要交付的机器总共需要多少钱，而不考虑第i周会给第K或者第K+1周生产的机器所产生的成本——这部分内容我们到计算第K周/第K+1周成本的时候，再加进去。在这个定义下，问题是符合最优子结构的

往简单点说，就是转变一下思路，交付的时候再算总账，而不是生产的时候就预估成本

希望这么解释可以让你明白一些，有什么不清楚的可以继续提问