17動態規劃-最小旅行開銷問題
問題描述：
給定一個陣列，包含的值為一年內需要旅行的日期（以天數為基準），給定三種通行證cost[0],cost[1],cost[2]，分別可以使用1天，使用7天，使用30天，設計本年旅行的最小開銷出行方式，
問題分析：
每天都有4中情況：1 當天不出門，則不買票最好，2 當天要出門，則可以買三種型別的票，由于每種票的使用期限不同，因此買每種票對應后面的數天內，可以不需要買票，
定義dp[i]為前i天最小出行開銷，如果第i天需要出行，則從第i天，分別往前推1、7、30天內的旅行，都可以通過某張票解決，再往前推，即分別為dp[i-1]、dp[i-7]、dp[i-30]，如果第i天不出行，則第i天不開銷，因此可以得到狀態轉移方程：
dp[i]=min( dp[i-1]+cost[i]，dp[i-7]+cost[2]，dp[i-30]+cost[2] )，第i天出行；
dp[i]=dp[i-1]，第i天不出行；
此類問題為分類選擇問題(三種通行證可以選擇)，可以基于不同類別下的引數定義模型，并找出其中的關系，進行處理，
演算法代碼：
int travelcost(int cost[2], int day[10]) {
int n=day[9];
int dp[10] = {0}, j = 1;
int a, b, c;
for (int j = 0; j < 9; j++)//利用初值來標記出行的天
dp[day[j]] = -1;
for (int i = 0; i <=n; i++) {
if (dp[i] == 0)
dp[i] = dp[i - 1];
else {
a = dp[i - 1] + cost[0];
if (i >= 7)
b = dp[i - 7] + cost[1];
else b = cost[1];
if (i>= 30)
c = dp[i - 30] + cost[2];
else c = cost[2];
}
dp[i] = min(a, b);
dp[i] = min(dp[i], c);
}
return dp[10];
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/212523.html
標籤：其他
上一篇：第七章 Shell腳本應用（三）