假设我们要从A行驶到B，在行驶过程中，有一些加油站d_1，...，d_n，其中d_1 = A，d_n = B，我们可以选择在每个加油站加燃料C_i，假设如果在d_i站添加天然气，那么我们可以将a_i行驶更多公里。我想找到一种动态编程算法，以找到前往B的最低成本（假设存在这样的序列）。
我尝试使用D [i]作为从A到第i站的最低费用，但是我在弄清楚递归关系方面遇到麻烦。我认为我可能需要跟踪我们目前可以旅行多长时间。但这太复杂了...
如您所说，您可能需要跟踪我们目前可以旅行多长时间。您应使用D [i] [j]作为从A到第i站并留下j公里燃料的最低费用。在这种情况下，递归关系变为下面。
D[i][j] = min( min{ D[i-k][j+(d_i - d_{i-k})] | k<i }, D[i][j-a_i] + C_i );
第一项min{ D[i-k][j+(d_i - d_{i-k})] | k<i }是指以(d-i - d_{i-k})几公里的油耗从ik站移至i站。k可以取0到i-1的值。
第二项D[i][j-a_i] + C_i意味着在d_i站增加a_i公里的天然气，并消耗C_i成本。另外，如果您允许在同一站点多次添加气体，则必须小心。
最后，min{ D[n][*] | '*' is any positive value }成为答案。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句