CODEWITHSUNDEEP
javaalgorithmcombinationsdynamic-programmingcombinatorics
JohnDow
JohnDow

Reputation: 1322

Dynamic programing / Combinations without repetitions and order is not important

Let's say we have some railroad with length L. We need to place K service stations between the first and last kilometer of this railroad. Service stations on 0 and L km's are already build for free. Given are the price of building a service station at every kilometer of this railroad and the equation to calculate the price of service for a given length of railroad.

For example, we have 4 km railroad, and get list of prices to build one station at the n'th km of railroad : 

5 22 13

also we have equation for service between stations - PRICE(len) = 2 * len*len + 3*len.

So, we need to build 1 station, we can do this on:

1st km - it will cost 5 for building and PRICE(1)=5 (service from 0 to 1 km) + PRiCE(3)=27 (service from 1 to 4 km) => 37

2st km - it will cost 22 for building and PRICE(2)=14 (service from 0 to 2 km) + PRiCE(2)=14 (service from 2 to 4 km) => 50

3st km - it will cost 13 for building and PRICE(3)=27 (service from 0 to 3 km) + PRiCE(1)=5(service from 3 to 4 km) => 69

Best option is to build 1 station on first km.

What if we need to build 2 stations?

 |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

So, best way is to place two stations at first and third km.

My task is to find minimum price for given length, number of stations to build, prices to build station on specific km and equation.

My idea was to calculate len table to know cost to maintain specific length. For given example it is table:

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

Then I calculate table with cost to build any two stations on specific kilometers:

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

So, then I just create recursion and go thru this like this:

 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);                
        }
    }

I start with calling it with 0 cost, level is number of station left to build and idx is pointer to last building station.

Biggest problem is that for example for L = 200 and 50 stations there is 4.538583779232459e+47 combinations, and I don't think I am doing good going through every combination. Of course I cut something cost < min, but it is still super slow and I think I am just missing something.

I have the feeling that I can break this into sub-problems.

Original problem in Czech: https://cw.felk.cvut.cz/courses/a4b33alg/task.php?task=servis

Upvotes: 2

Views: 216

Answers (1)

Fallen
Fallen

Reputation: 4565

First, note that for any position x, if we already have calculated the result putting the last station on yth km, y < x, result from x or right will not depend on the choices of the stations before y. So the state of the DP solution will be [KM][position_of_last_station][station_already_built]

Sample code is following:

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;

}

Complexity analysis: Will require O(MAX_KM * MAX_KM * MAX_STATION) time and space

Warning: Code's not tested

Upvotes: 1

Related Questions