算法课的课堂测试,问题大概就是这些描述。
动态规划旅游问题:汽车加满油可以跑n千米,中途有若干个加油站,请用动态规划的方式求解中途加油次数最少的方案。
我的代码:
#include<iostream>using namespace std;const int car = 10;//汽车加满油后的续航里程void travel(int gasNumber[], int weight[], int count){if (car < weight[0]){cout<<"汽车续航太差,加满油都无法到达下一个加油站。"<<endl;return;}for (int i=1; i<count; i++){if ((weight[i]+weight[i-1])>car){gasNumber[i] = 0;//标记0为需要中途加油的加油站}else{weight[i] += weight[i-1];//将weight[i-1]累加到weight[i]中}}//打印需要中途加油的加油站编号for (int i=0; i<count; i++){if (gasNumber[i]==0){cout<<"在"<<i+1<<"号加油站加油"<<endl;}} }int main(){int gasNumber[4] = {1,2,3,4};//加油站编号int weight[4] = {5,6,2,9};//1号加油站离2号加油站距离为5,2号加油站离3号加油站距离为6,3号加油站离4号加油站距离为2,4号加油站离终点距离为9int count = sizeof(gasNumber)/sizeof(int);//gasNumber数组的长度,也就是加油站的数量travel(gasNumber, weight, count);return 0;}
动态规划旅游问题:汽车加满油可以跑n千米 中途有若干个加油站 请用动态规划的方式求解中途加油次数最少的方案。