旅游预算（动态规划） noj 西工大算法

旅游前规划好预算，避免超支 #生活常识# #消费指南#

        本人为23届鼠鼠，这道算法题前前后后花了不少时间来解答（菜），弄明白后激动万分，写下此篇文章记录，同时也是为了防止以后忘记。

题目概述

摘自实验课的头歌

变量定义

contain：容量        len:总路程         dist[i]:加油站i距起点的距离        price[i]:加油站i的油价

prior[i]:到达i的最优解中，上一个加油的加油站（比如最优解是先在1加油，然后再在3加油，最后直达终点，那么prior[n+1]=3,prior[3]=1,prior[1]=0）

f[i]:动态规划数组

令起点为0号加油站，终点为n+1号加油站。

错误想法       

        先分享一下本人之前的错误想法（困惑了一会）：假设数组f[i]表示到达第i个加油站的最小费用，（f[0]表示起点，f[n+1]表示中点）。由于是动态规划，所以假设f[1到i-1]都已经解决，那么f[i]就应当是遍历之前的所有点，即f[j],如果j点可以中途不加油，直接到达i点，就按照规则加油尝试，取最小的更新prior和f数组，即：

for (int i = 1; i <= n + 1; i++) {

double mini = 999999.9;

for (int j = i - 1; j >= 0; j--) {

if (canArrive(j, i) && canAddOil(j)) {

double tmp = f[j] + price[j] * (contain - remain[j]) + 2;

if (j == 0)tmp -= 2;

if (tmp < mini) {

mini = tmp;

prior[i] = j;

remain[i] = contain - (dist[i] - dist[j]) / perable;

}

}

}

f[i] = mini;

}

        采用这种写法时，我通过了四个数据，但是一组数据没有通过。后来才反应过来，中途路过并且加油的加油站，并不需要是到达那一个加油站的最优解。以未通过的测例来说明：

如果以3为终点，若先在起点加满一次，再在1号加油站加满一次，花费是27.5元。如果是先在起点加满一次，再在2号加满一次，花费是29.几元。因此我们发现，如果只是单纯的想到达3号加油站，在2号加油站并不是最好的选择，但是如果是到达终点，在2号加油站却是最优（39.15<40.22）的。

        因为你仅仅考虑到达，却不考虑到达后还剩多少了，对后面的影响也都忽略了，因此产生了错误。比如说我虽然到达了这个加油站，并且花掉了最少的钱，但是，如果其他方法也到达了，虽然花的钱多了一点，但是他剩下的油多，你就不能否定他是到达后面终点的最优解路径之一。

AC的代码

        上述算法是错误的，那么是不是说明不可以动态规划了呢？不。只需要稍作修改即可。错误的想法是f[i]为到达i号加油站的最小花费。我们把它改成，f[i]表示到达i号加油站，并且在这里把油再次加满，总共所花费用的最优解。这样就可以解决之前顾前不顾后的问题了。

        注意到题目在i点可以加油的条件，构造如下函数：

bool canAddOil(int start, int end) {

double s = dist[end] - dist[start];

double remain = contain - s / perable;

if (remain <= contain / 2)return true;

else if (remain * perable < dist[end + 1] - dist[end])return true;

return false;

}

表示从start开始（对应j），到达end加油站（对应i)，如果到达end后，在end可以加油，则返回真，否则返回假。

        核心代码如下：

for (int i = 1; i <= n+1; i++) {

f[i] = 999999.9;

}

for (int i = 1; i <= n + 1; i++) {

for (int j = i - 1; j >= 0 && dist[i] - dist[j] <= contain * perable; j--) {

if (canAddOil(j,i)) {

double tmp = f[j] + (dist[i] - dist[j]) / perable * price[i] + 2;

if (tmp < f[i]) {

f[i] = tmp;

prior[i] = j;

}

}

}

}

有一个很巧妙的地方是，根据修改后的转移方程，前面的每一个点j都加满油了，因此，在i点加油所花费的价钱就是(dist[i] - dist[j]) / perable * price[i]，因此不需要其他额外的数组记录每点所剩余的油量。为了方便的处理终点，我们把终点也抽象为一个加油站(n+1)号加油站，只不过dist[n+1]=len, 并且price[n+1]=0,即终点虽然不用再加满油了，为了不影响结果和代码的一致性，把它变成一个免费的加油站，这样不用特殊处理就可以得到答案，注意在终点不需要那个额外的两元钱了，f[n+1]-2才算是最终结果。

完整代码（头歌有查重，仅供参考）

#include <iostream>

#include <vector>

using namespace std;

int n;

double perable;

double dist[55];

double price[55];

double len;

double contain;

int prior[55];

double f[55];

bool canAddOil(int start, int end) {

double s = dist[end] - dist[start];

double remain = contain - s / perable;

if (remain <= contain / 2) return true;

else if (remain * perable < dist[end + 1] - dist[end]) return true;

return false;

}

int main() {

cin >> len >> contain >> perable >> f[0] >> n;

for (int i = 1; i <= n; i++) {

cin >> dist[i] >> price[i];

}

dist[n + 1] = len;

price[n + 1] = 0;

for (int i = 1; i <= n + 1; i++) {

f[i] = 999999.9;

}

for (int i = 1; i <= n + 1; i++) {

for (int j = i - 1; j >= 0 && dist[i] - dist[j] <= contain * perable; j--) {

if (canAddOil(j, i)) {

double tmp = f[j] + (dist[i] - dist[j]) / perable * price[i] + 2;

if (tmp < f[i]) {

f[i] = tmp;

prior[i] = j;

}

}

}

}

vector<int> path;

int i = prior[n + 1];

while (i != 0) {

path.push_back(i);

i = prior[i];

}

printf("%.2f ", f[n + 1] - 2);

cout << path.size() << endl;

for (int i = path.size() - 1; i >= 0; i--) {

cout << path[i] << ' ';

}

}

网址：旅游预算（动态规划） noj 西工大算法 https://www.yuejiaxmz.com/news/view/477447

相关内容

新加坡七日游，预算规划与旅行攻略
旅游预算怎么制定(如何做旅游预算)
新加坡旅游一星期，预算规划与旅行建议
云南旅游攻略：如何规划行程、节省预算及注意事项，让你的旅行更划算
算法动态规划01背包问题
云南旅游省钱攻略：如何规划预算并享受美食与自然风光
为外出旅游做预算
动态规划算法在生活中的应用
旅行预算规划技巧与省钱策略分享
NOJ

随便看看