这是一个典型的贪心策略问题。为了使得总成本最小,我们应该优先使用价格最低的发货日期。
问题的关键在于,一个订单有多个可选的发货日期(只要在最晚发货日期之前),而一个发货日期也可以被多个订单使用(只要不超过当天的发货上限)。
一个直观且正确的贪心思路是按时间顺序来处理。我们从第 1 天开始,一直到第 n 天。在每一天 i,我们会遇到两件事:
多多有一批订单需要发货,每个订单都存在独立的最晚发货日期,需要在那之前发出。
多多找了一家合作的物流商,物流商给出了未来一段时间每天的发货价格,并且每天最多能发的包裹数量是有限的。
多多需要在每个订单的最晚发货日期前将所有订单发出,并尽可能减少发货成本。