algorithm - 找到最低票价

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。
• 否则，最低成本涉及以下之一:
  • 第 d 天的 1 天通行证。在这种情况下，MC(d) = MC(d - 1) + 2。
  • 7 天通行证在第 d 天或之后结束。在这种情况下，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 .