Dynamic programming interval scheduling with time between jobs

Question

I'm trying to program the interval scheduling problem with dynamic programming. All jobs have different (positive) weights and don't overlap. These weights represent different run times. An idle time of three "gaps" may exist between jobs. Furthermore, each time unit for each job (in seconds) takes one resource. The resources can all have different values. I want to find the smallest sum of resources for all jobs with a dynamic programming algorithm (recursively).

It may be more clear with an example:

Let's say you have three jobs with time units { 2, 2, 3 } and you have a list of resources of eight long { 2, 5, 1, 8, 4, 1, 1, 5 }. Job one takes two time units and thus two resources, and because it's the first job it will take the first 2 resources of the resources-list. Job two doesn't have to start immediately after job one, it can also start from one of the next three "gaps". This second job takes also two resources and because it can start from one of the three gaps and it's not the first job, the possibilities of resources that it can take are (1,8) (8,4) (4,1) (1,1) = 9 12 5 2 (the different sums of the available resources). The sum of all jobs is of course less than the number of resources.

This is continued until all jobs are finished. I want to find the smallest sum of resources for all jobs with a dynamic programming algorithm (recursively).

I tried different solving methods, but I find this one very hard to solve recursively without any other function.

I did write the following code, which is not doing as I expected:

public static double getCost(int t, int q, int r, int[] jobs, double[] resources){
    double table[][] = new double[t+1][r+1];
    for(int i = 0;i < t;i++){
        for(int j = 0;j < r;j++){
            double cost = 0;
            for(int k = j-jobs[i] + 1;k <= j;k++){
                if(k < 0){
                    break;
                }
                cost = cost + resources[k];
            }
            double min = Double.POSITIVE_INFINITY;
            for(int l = 1;l <= q;l++){
                if(i == 0 && l == 1){
                    min = cost+j-jobs[0]-l;
                }
                else{
                    double neww = cost+j-jobs[i]-l;
                    if(neww < min){
                        min = neww;
                    } 
                }
            }
            table[i+1][j+1] = min;
        }
    }
    return table[t][r];
}

Can someone please give me some advice?

Answer 1

First, you need to define the state for each subproblem, so:

sum[t][r] = Minimum cost using up to 't' indexes in 'timeUnits',
            and 'r' indexes in 'resources' (exclusive indexes).

The base case is:

sum[0][0] = 0

Then update the array values based on previous values. There are two things to calculate: the cost of running a job, and what to add it on to (gap size).

For each t
  For each r
    cost = Sum(resources[i]) for i = r-timeUnits[t]+1 ... r
    sum[t+1][r+1] = Min(cost + sum[t][r-timeUnits[t]-gap+1]) for gap = 0 ... 2 (0 only for t=0)

The final cost is the minimum value where all time units are used.

Edit: I modified your code so that it passed your test case.

int[] jobs = { 2, 2, 2 };
int[] resources = { 1, 2, 3, 4, 5, 6, 7, 8, 1, 1 };
int q = 2;
int t = jobs.length;
int r = resources.length;

double table[][] = new double[t+1][r+1];

for(int i = 0;i <= t;i++){
    for(int j = 0;j <= r;j++){
        table[i][j] = Double.POSITIVE_INFINITY;
    }
}
table[0][0] = 0;

for(int i = 0;i < t;i++){
    for(int j = 0;j < r;j++){
        double cost = 0;
        for(int k = j-jobs[i] + 1;k <= j;k++){
            if(k < 0){
                cost = Double.POSITIVE_INFINITY;
                break;
            }
            cost = cost + resources[k];
        }

        double min = Double.POSITIVE_INFINITY;
        for(int l = 0;l <= q;l++) {
            int index = j-jobs[i]-l+1;
            if(index >= 0 && index <= r) {
                min = Math.min(min, cost + table[i][index]);
            }
            if(i == 0) break;
        }

        table[i+1][j+1] = min;
    }
}

double best = Double.POSITIVE_INFINITY;
for(int x = 0; x < r; x++) {
    best = Math.min(best, table[t][x+1]);
}

System.out.println("Best cost: " + best);