java - 没有重复和顺序的动态规划/组合并不重要

Question

假设我们有一条长度为 L 的铁路。我们需要在这条铁路的第一公里和最后一公里之间放置 K 个服务站。 0 和 L 公里的服务站已经免费 build 。给定这条铁路每公里 build 一个服务站的价格，以及计算给定铁路长度的服务价格的方程式。

例如，我们有 4 公里的铁路，并获取在铁路的第 n 公里处 build 一个车站的价格表:

5 22 13

我们还有站间服务方程式 - PRICE(len) = 2 * len*len + 3*len.

所以，我们需要 build 1站，我们可以在:

1st km - 建筑费用为 5，PRICE(1)=5(0 到 1 公里的服务)+ PRiCE (3)=27(服务距离为 1 至 4 公里)=> 37

2st km - 建筑费用为 22，PRICE(2)=14(0 到 2 公里的服务)+ PRiCE (2)=14(服务距离为 2 至 4 公里)=> 50

3st km - 建筑费用为 13，PRICE(3)=27(0 到 3 公里的服务)+ PRiCE (1)=5(服务距离为 3 至 4 公里)=> 69

最好的选择是在第一公里处 build 1站。

如果我们需要 build 2站怎么办？

 |S|_|_|_|F|

 |S|1|2|_|F|  5+22+PRICE(1)+PRICE(1)+PRICE(2) = 5 + 22 + 5 + 5 + 14 = 51 
 |S|1|_|3|F|  5+13+PRICE(1)+PRICE(2)+PRICE(1) = 5 + 13 + 5 + 14 + 5 = 42
 |S|_|2|3|F|  22+13+PRICE(2)+PRICE(1)+PRICE(1) = 22 + 13 + 14 + 5 + 5 = 59

所以，最好的办法是在第一公里和第三公里处设置两个站点。

我的任务是找出给定长度的最低价格、要 build 的车站数量、在特定公里和等式上 build 车站的价格。

我的想法是计算 len 表以了解维持特定长度的成本。对于给定的示例，它是表:

+------+------+------+------+
| idx0 | idx1 | idx2 | idx3 |
+------+------+------+------+
|    0 |    5 |   14 |   27 |
+------+------+------+------+

然后我计算了在特定公里数上 build 任意两个站点的成本表:

╔══════╦══════╦══════╦══════╦══════╗
║      ║ idx0 ║ idx1 ║ idx2 ║ idx3 ║
╠══════╬══════╬══════╬══════╬══════╣
║ idx0 ║      ║      ║      ║      ║
║ idx1 ║      ║    5 ║   32 ║   32 ║
║ idx2 ║      ║      ║   22 ║   40 ║
║ idx3 ║      ║      ║      ║   13 ║
╚══════╩══════╩══════╩══════╩══════╝

所以，我只是创建递归并像这样进行:

 public static void recur(int cost, int level, int idx) {
        if (level == 0) {
            if (min > cost + len[delka - idx]) {
                min = cost + len[delka - idx];
                System.out.println(min);
            }

        }
        if (level > 0 && cost < min) {
            for (int i = idx; i <= delka - level; i++) {
                recur(cost + d[idx][i], level - 1, i);                
        }
    }

我以 0 成本开始调用它，level 是剩余要 build 的车站数量，idx 是指向最后 build 车站的指针。

最大的问题是，例如，对于 L = 200 和 50 个站，有 4.538583779232459e+47 种组合，我认为我在遍历每一种组合时都做得不好。我当然剪了东西cost < min ，但它仍然非常慢，我想我只是错过了一些东西。

我觉得我可以将其分解为子问题。

捷克语的原始问题:https://cw.felk.cvut.cz/courses/a4b33alg/task.php?task=servis

Answer 1

首先，请注意对于任何位置 x，如果我们已经计算出将最后一个站点放在第 y km 上的结果，则 y < x，结果从 x 或右将不取决于 y 之前站点的选择。所以 DP 解决方案的状态将是 [KM][position_of_last_station][station_already_built]

示例代码如下:

int memo[MAX_KM][MAX_KM][MAX_STATION];
bool seen[MAX_KM][MAX_KM][MAX_STATION]; // if seen[km][pos_of_last_station][station_remaining] is true 
                                         // then this subproblem has already been solved. No need to solve it again

int dp(int KM, int pos_of_last_station, int station_remaining) {
    if(KM == MAX_KM + 1) {
        // reached the end
        int len = (MAX_KM - pos_of_last_station);
        return 2 * len * len + 3 * len;
    }

    if(seen[KM][pos_of_last_station][station_remaining]) {
        // this sub problem has already been solved
        return memo[KM][pos_of_last_station][station_remaining];
    }
    int ret = 2e9; // some large value
    if(station_remaining > 0) {

        // trying establishing a station on the current position
        int len = KM - pos_of_last_station;
        ret = min(ret, dp(KM + 1, KM, station_remaining - 1) + (2 * len * len + 3 * len) + cost[KM] );  // assuming cost[KM] is the cost to establish a station on KMth kilometer
    }
    ret = min(ret, dp(KM + 1, pos_of_last_station, station_remaining) );
    seen[KM][pos_of_last_station][station_remaining] = true; // sub problem visited
    memo[KM][pos_of_last_station][station_remaining] = ret;  // storing the result for future utilization

    return ret;

}

复杂度分析:会需要O(MAX_KM * MAX_KM * MAX_STATION)时间和空间

警告:代码未经测试