[解決済み] ガソリンスタンドダイナミックプログラミング

質問

あなたは友人と一緒に春休みにティファナへドライブに行くことになりました。あなたは旅行のためのお金を節約しているので、途中のガソリン代を最小限に抑えたいと考えています。ガソリン代を最小限に抑えるために、あなたとあなたの友人は次の情報をまとめました。まず、あなたの車はガソリン1タンクで確実にmマイル走行できる（ただし、それ以上は無理）。あなたの友人の一人がウェブからガソリンスタンドのデータを収集し、ルート上のすべてのガソリンスタンドとそのガソリンスタンドの価格をプロットしています。具体的には、最も近いところから遠いところまでのn+1個のガソリンスタンドの価格と、隣接する2つのガソリンスタンド間のn個の距離のリストを作成しました。タコマはガソリンスタンド番号0、ティファナはガソリンスタンド番号nです。便宜上、ガソリン代は車で移動したマイルあたりの値段に変換されています。さらに、隣接する2つのガソリンスタンド間の距離（マイル）も計算されています。あなたはガソリンを満タンにして旅を始め、ティファナに着いたら帰りのためにガソリンを満タンにします。旅のガソリン代を最小限にするために、どのガソリンスタンドに立ち寄るかを決定する必要があります。

サンプル入力です。

価格（セント／マイル） [12,14,21,14,17,22,11,16,17,12,30,25,27,24,22,15,24,23,15,21]

距離(マイル) [31,42,31,33,12,34,55,25,34,64,24,13,52,33,23,64,43,25,15]

あなたの車はガソリン1本で170マイル走行可能です。

私の出力

旅行代金の最小値：117.35ドル

立ち寄るガソリンスタンド [1, 6, 9, 13, 17, 19]

すでに問題は解決しているのですが、やり方が正しいかどうかわかりません。どなたかご指摘、または間違っていたら正しい方向を示していただけませんか？よろしくお願いします。

public class GasStation {

/** An array of gas prices.*/
private int[] myPrice;
/** An array of distance between two adjacent gas station.*/
private int[] myDistance;
/** Car's tank capacity.*/
private int myCapacity;
/** List of gas stations to stop at to minimize the cost.*/
private List<Integer> myGasStations;


/**
 * A constructor that takes in a price list, distance list, and the car's tank capacity.
 * @param thePrice - price list
 * @param theDistance - distance list
 * @param theCapacity - the car's capacity
 */
public GasStation(final int[] thePrice, final int[] theDistance,
        final int theCapacity) {
    myPrice = thePrice;
    myDistance = theDistance;
    myCapacity = theCapacity;
    myGasStations = new ArrayList<>();
}


/**
 * Calculate for the minimum cost for your trip.
 * @return minimum cost
 */
public int calculateMinCost() {

    int lenP = myPrice.length;
    int lenD = myDistance.length;
    if (lenP == 0 || lenD == 0 || myCapacity == 0) return 0;

    // gas station -> another gas station (moves) 
    Map<Integer, Integer> gasD = new HashMap<>();
    int[] D = new int[lenD + 1];
    D[0] = 0;

    // calculate the total distance 
    for (int i = 0; i < lenD; i++) {
        D[i + 1] = D[i] + myDistance[i];
    }

    int len = D.length;
    for (int i = 1; i < len - 1; i++) {
        int j = len - 1;
        while (D[j] - D[i] >= myCapacity) {
            j--;
        }
        gasD.put(i, j - i);
    }

    int min = Integer.MAX_VALUE;

    for (int i = 1; i < len; i++) {
        int temp = 0;
        int cur = i;
        List<Integer> tempList = new ArrayList<>();
        if (D[i] <= myCapacity) {
            temp = D[cur] * myPrice[cur];
            tempList.add(cur);
            int next = gasD.get(cur) + cur;
            while (next < len) {
                temp += (D[next] - D[cur]) * myPrice[next];
                cur = next;
                tempList.add(cur);
                if (gasD.containsKey(cur)) next = gasD.get(cur) + cur;
                else break;
            }

            if (temp < min) {
                min = temp;
                myGasStations = tempList;
            }

        }
    }


    return min;
}

/**
 * Get gas stations to stop at.
 * @return a list of gas stations to stop at
 */
public List<Integer> getGasStations() {
    return myGasStations;
}

}

解決方法は？

での詰め替えの最小コストとする。 station i と表記されます。 cost[i]

問題文がある場合、このコストはどのように表現できるでしょうか？
次の補充はすべて、以下の時間内に行わなければならないことが分かっています。 170 miles 最後のリフィルから離れた場所。
ということは、最小コストは次のように表現できる。

cost[i] = MIN { cost[j] + price[i] * distance_from_i_to_j } for every j such that distance(i,j) <= 170 mi

ベースケース付き cost[0] = 0 での満タンコストを考えないと、このようなことになります。 station 0 それ以外の場合、ベースケースは cost[0]= 170 * price[0]

で満タンコストは考えないことにします。 station 0 また、最終地点での補充は必要ないものとします。 station 19

上で定義された再帰関係を見てみると、同じ部分問題が複数回呼び出されていることに容易に気づくだろう。これは、指数関数的な実行時間を避けるために、動的計画法を利用することができることを意味している。

での補充が必要ないことにも注意してください。 station 19 での給油のコストを計算する必要があります。 1 を通して 18 のみで、つまり cost[1], cost[2], .., cost[18] . そうすると、問題の答えは次のようになります。 MIN { cost[14], cost[15], cost[16], cost[17], cost[18] } から170マイル以内にある駅だけだからです。 station 19 は駅 14,15,16,17,18 ということで、駅に着くかもしれません。 19 この5つのステーションのうち1つで補給することで

上記の基本ケースによる漸化式を定義した後、以下の方法でループに変換することができる。

int price[] =  {12,14,21,14,17,22,11,16,17,12,30,25,27,24,22,15,24,23,15,21}; //total 20 stations

int distance[] = {31,42,31,33,12,34,55,25,34,64,24,13,52,33,23,64,43,25,15};  //total 19 distances      

int N=19;
int[] cost = new int[N];    
int[] parent = new int[N]; //for backtracking

cost[0] = 0; //base case (assume that we don't need to fill gas on station 0)

int i,j,dist;
int maxroad = 170;

for(i=0; i<N; i++) //initialize backtracking array
    parent[i] = -1;


for(i=1; i<=N-1; i++) //for every station from 1 to 18
{

        int priceval = price[i]; //get price of station i               
        int min = Integer.MAX_VALUE;                
        dist = 0;            

        for(j=i-1; j>=0; j--) //for every station j within 170 away from station i
        {   
            dist += distance[j]; //distance[j] is distance from station j to station j+1
            if(dist>maxroad)
               break;   

            if((cost[j] + priceval*dist)<min) //pick MIN value defined in recurrence relation                       
               {
                min = cost[j] + priceval*dist;
                parent[i] = j;
               }

        }

        cost[i] = min;              

}


//after all costs from cost[1] up to cost[18] are found, we pick
//minimum cost among the stations within 170 miles away from station 19
//and show the stations we stopped at by backtracking from end to start

int startback=N-1;
int answer=Integer.MAX_VALUE;
i=N-1;
dist=distance[i];
while(dist<=maxroad && i>=0)
{
   if(cost[i]<answer)
      {
       answer = cost[i];
       startback=i;
      }  
   i--;
   dist += distance[i];
}


System.out.println("minimal cost=" + answer + "\nbacktrack:");

i=startback;
while(i>-1) //backtrack
{
    System.out.println(i + " ");
    i = parent[i];
}