本题是一个变形的背包问题:每个包裹可以选择两种“花费”(燃料),其中一种会额外消耗 1 张通行证。目标是先最大化派送包裹数,在此基础上最小化燃料消耗,并满足燃料 ≤ X、通行证 ≤ Y。
算法:动态规划(DP,二元约束下的最优化-可行性分离)
dp[j][k] 表示在处理若干包裹后,恰好派送 j 个包裹、使用 k 张通行证时的最小燃料。
初始化:dp[0][0] = 0,其余为正无穷。星际快递公司有 N 个包裹需要派送,每个包裹有两种派送方式!
1、常规派送(消耗较多燃料)
2、虫洞派送(使用一个虫洞通行证,可以以消耗较少燃料的情况下完成派送)
当前快递飞船携带了 X 单位的燃料和 Y 张虫洞通行证。