Блог

Допустим, у нас есть некоторая железная дорога длиной L. Нам нужно разместить K станций технического обслуживания между первым и последним километром этой железной дороги. Станции технического обслуживания на 0 и L км уже построены бесплатно. Даны цена строительства станции технического обслуживания на каждом километре этой железной дороги и уравнение для расчета цены обслуживания для заданной длины железной дороги.

Например, у нас есть 4 км железной дороги, и мы получаем список цен на строительство одной станции на n-м километре железной дороги :

 5 22 13
  

также у нас есть уравнение для обслуживания между станциями — PRICE(len) = 2 * len*len 3*len.

Итак, нам нужно построить 1 станцию, мы можем сделать это на:

1-й км — это будет стоить 5 для построения и ЦЕНА (1) = 5 (обслуживание от 0 до 1 км) Цена (3) = 27 (обслуживание от 1 до 4 км) => 37

2-й км — это будет стоить 22 для построения и ЦЕНА (2) = 14 (обслуживание от 0 до 2 км) Цена (2) = 14 (обслуживание от 2 до 4 км) => 50

3-й км — это будет стоить 13 для построения и ЦЕНА (3) = 27 (обслуживание от 0 до 3 км) Цена (1) = 5 (обслуживание от 3 до 4 км) => 69

Лучший вариант — построить 1 станцию на первом километре.

Что, если нам нужно построить 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
  

Итак, лучший способ — разместить две станции на первом и третьем км.

Моя задача — найти минимальную цену за заданную длину, количество станций для сборки, цены на строительство станции на конкретном километре и уравнение.

Моя идея состояла в том, чтобы рассчитать таблицу len, чтобы узнать стоимость поддержания определенной длины. Для данного примера это таблица:

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

Затем я вычисляю таблицу со стоимостью строительства любых двух станций на определенных километрах:

 ╔══════╦══════╦══════╦══════╦══════╗
║      ║ 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 amp;amp; cost < min) {
            for (int i = idx; i <= delka - level; i  ) {
                recur(cost   d[idx][i], level - 1, i);                
        }
    }
  

Я начинаю с вызова его с 0 cost, level — это номер станции, оставшейся для сборки, а idx — указатель на последнюю строительную станцию.

Самая большая проблема заключается в том, что, например, для L = 200 и 50 станций существует 4.538583779232459 комбинаций e 47, и я не думаю, что у меня все хорошо получается, просматривая каждую комбинацию. Конечно, я что-то вырезал cost < min , но это все еще очень медленно, и я думаю, что я просто что-то упускаю.

У меня такое чувство, что я могу разбить это на подзадачи.

Оригинальная проблема на чешском языке: https://cw.felk.cvut.cz/courses/a4b33alg/task.php?task=servis

Во-первых, обратите внимание, что для любой позиции x, если мы уже вычислили результат, поместив последнюю станцию на y-й км, y < x, результат от x или справа не будет зависеть от выбора станций перед y. Таким образом, состояние решения DP будет [KM][position_of_last_station][station_already_builded]

Пример кода следующий:

 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) времени и пространства

Предупреждение: код не протестирован