我正在尝试使用动态规划对区间调度问题进行编程。所有工作都有不同的(正)权重并且不重叠。这些权重代表不同的运行时间。作业之间可能存在三个“间隙”的空闲时间。此外,每个作业的每个时间单位(以秒为单位)占用一个资源。这些资源都可以有不同的值。我想用动态规划算法(递归)为所有作业找到最小的资源总和。
举个例子可能更清楚:
假设您有三个具有time units { 2, 2, 3 }
的作业,并且您有一个八长{ 2, 5, 1, 8, 4, 1, 1, 5}
。作业一需要两个时间单位,因此需要两个资源,因为它是第一个作业,所以它将占用资源列表的前 2 个资源。作业二不必在作业一之后立即开始,它也可以从接下来的三个“间隙”之一开始。第二个工作也需要两个资源,因为它可以从三个间隙之一开始,而不是第一个工作,它可以使用的资源的可能性是 (1,8) (8,4) (4, 1) (1,1) = 9 12 5 2
(可用资源的不同总和)。所有工作的总和当然小于资源的数量。
这一直持续到所有作业完成。我想用动态规划算法(递归)为所有作业找到最小的资源总和。
我尝试了不同的求解方法,但我发现这个方法在没有任何其他函数的情况下很难递归求解。
我确实写了下面的代码,但它并没有像我预期的那样:
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];
}
有人可以给我一些建议吗?
最佳答案
首先,您需要为每个子问题定义状态,因此:
sum[t][r] = Minimum cost using up to 't' indexes in 'timeUnits',
and 'r' indexes in 'resources' (exclusive indexes).
基本情况是:
sum[0][0] = 0
然后根据以前的值更新数组值。有两件事需要计算:运行作业的成本,以及将其添加到什么(差距大小)。
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)
最终成本是使用所有时间单位的最小值。
编辑:我修改了您的代码,使其通过了您的测试用例。
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);
关于algorithm - 动态编程间隔调度与作业之间的时间,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13991620/