查找最低票价

Question

查找在该月的已知日期(1 ... 30)购买旅行所需的最低票价.提供三种类型的门票:1天有效期为1天,2天有效,7天有效7天,7天,30天有效30天,25个单位.

例如:我想在一个月的[1,4,6,7,28,30]天旅行,即每月的第1天,第4天,第6天.......如何购买门票,使成本最低.

我尝试使用动态编程来解决这个问题,但解决方案并没有给我所有案例的正确答案.这是我在Java中的解决方案:

public class TicketsCost {
    public static void main(String args[]){
        int[] arr  =  {1,5,6,9,28,30};
        System.out.println(findMinCost(arr));
    }
    public static int findMinCost(int[] arr) {
        int[][] dp = new int[arr.length][3];
        int[] tDays = {1,7,30};
        int[] tCost = {2,7,25};

        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < 3; j++) {
                if (j==0){
                    dp[i][j]= (i+1)*tCost[j];
                }
                else{
                    int c = arr[i]-tDays[j];
                    int tempCost = tCost[j];
                    int k;
                    if (c>=arr[0] && i>0){
                        for (k = i-1; k >= 0; k--) {
                            if (arr[k]<=c){
                                c = arr[k];
                            }
                        }
                        tempCost += dp[c][j];
                        int tempCostX =  dp[i-1][j] + tCost[0];
                        tempCost = Math.min(tempCost,tempCostX);

                    }
                    dp[i][j] = Math.min(tempCost,dp[i][j-1]);
                }
            }
        }
        return dp[arr.length-1][2];
    }
}

该解决方案不适用于{1,7,8,9,10}输入,它给出10但正确答案应为9.此外,对于{1,7,8,9,10,15}它给出13但正确的是11.我已经发布了我的解决方案,不是为了我调试它而是仅供参考.我采用了自下而上的动态编程方法来解决这个问题.这种方法是否正确？

Answer 1

让MC(d)表示将在第1天到第d天为所有旅行支付的最低费用.然后,期望的答案是MC(30).

要计算MC(d),请注意以下事项:

• 如果第d天没有旅行,则MC(d)= MC(d  -1).
  • 作为一种特殊的情况下,MC(d)= 0对于所有d  ≤0.
• 否则,最低成本涉及以下之一:
  • A 1日通行证上天d.在这种情况下,MC(d)= MC(d  -1)+ 2.
  • 在第d天或之后结束的7天通行证.在这种情况下,MC(d)= min(MC(d  -7),MC(d  -6),...,MC(d  -1))+ 7.
    • 而且由于MC不减少(增加一天从不降低最低成本),这可以简化为MC(d)= MC(d  -7)+ 7.(帽子提示到Ravi指出这一点.)
  • 整个期间的30天通行证.在这种情况下,MC(d)= 25.

正如您所意识到的,动态编程(自下而上递归)非常适合这种情况.

为了便于编码,我建议我们首先将日期列表转换为"这是一个旅行日吗？"的查找表:

boolean[] isDayWithTrip = new boolean[31]; // note: initializes to false
for (final int dayWithTrip : arr) {
    isDayWithTrip[dayWithTrip] = true;
}

然后我们可以创建一个数组来跟踪最低成本,并从索引0开始填充它:

int[] minCostUpThroughDay = new int[31];
minCostUpThroughDay[0] = 0; // technically redundant
for (int d = 1; d <= 30; ++d) {
    if (! isDayWithTrip[d]) {
        minCostUpThroughDay[d] = minCostUpThroughDay[d-1];
        continue;
    }

    int minCost;
    // Possibility #1: one-day pass on day d:
    minCost = minCostUpThroughDay[d-1] + 2;
    // Possibility #2: seven-day pass ending on or after day d:
    minCost =
        Math.min(minCost, minCostUpThroughDay[Math.max(0, d-7)] + 7);
    // Possibility #3: 30-day pass for the whole period:
    minCost = Math.min(minCost, 25);

    minCostUpThroughDay[d] = minCost;
}

而且minCostUpThroughDay[30]是结果.

您可以在以下网址查看上述代码:https://ideone.com/1Xx1fd.