装配线调度递归解错误
基本上，我是以递归的方式解决装配线调度问题，基于提供的这里公式
可以从问题语句中提取以下信息，使其更简单：
两条装配线，1和2，每个装配线从1到n。
汽车底盘必须通过从1到n的所有车站(在两条装配线中的任何一条)。也就是说，它不能从站i跳到站j，如果它们不是在一个移动距离。
汽车底盘可以在同一条线上向前移动一个站，或在另一条线上向对角移动一个站。从第一行移动到站j需要额外的费用ti，j。在同一条线上移动不需要任何费用。
I线j站的时间是ai，j。
i，j代表I线上的一个站j。
将问题分解为较小的子问题:如果(i-1)第一个阶乘是已知的，我们很容易就能找到第一个阶乘。我们能在这里应用类似的funda吗？如果底盘离开站Si，j-1所需的最小时间已知，则通过结合ai、j和ti、j，可以快速计算出离开站Si、j所需的最小时间。
T1(j)表示汽车底盘离开装配线上j站所需的最短时间。
T2(j)表示汽车底盘离开装配线上j站所需的最短时间。
基本情况:进入时间ei只有当汽车底盘进入汽车厂时才进入画面。
第1行离开第一站所需的时间是: T1(1) =第1行的进入时间+站S1、1 T1(1) = e1 + a1,1类似地，第2行离开第一站所需的时间是: T2(1) = e2 + a2,1。
递归关系:如果我们看问题陈述，它很快归结为以下观察:站S1，j的汽车底盘可以来自站S1，j-1或站S2，j-1。
案例1:它以前的站是S1，j-1离开站S1的最小时间，j由: T1(j) =离开站S1的最小时间，j-1 +在站S1的时间，j T1(j) = T1(j-1) + a1，j。
案例2:它的前一站是S2，j-1离开站S1的最小时间，j由: T1(j) =离开站S2所需的最小时间，j-1 +改变装配线+在站S1中花费的额外费用，j T1(j) = T2(j-1) + t2，j+ a1，j。
最小时间T1(j)由在1和2中得到的最小时间T1(j) = min((T1(j-1) + a1，j)，(T2(j-1) + t2，j+ a1，j)所给出的最小时间，j由: T2(j) =min(T2(j-1)+ a2，j)，(T1(j-1) + t1，j+ a2，j)给出。
汽车底盘出厂所需的最小总时间是: Tmin =min(离开站Si所需时间，n+离开汽车厂所需时间) Tmin = min(T1(n) + x1，T2(n) + x2)。
动态编程版本是好的，但是，在我的递归版本中有一些隐藏的错误，有人能帮我找出这个错误吗？谢谢。
package DP;
public class AssemblyLineScheduling {
public static void main(String[] args) {
int[][] a = {{4, 5, 3, 2},
{2, 10, 1, 4}};
int[][] t = {{0, 7, 4, 5},
{0, 9, 2, 8}};
int[] e = {10, 12};
int[] x = {18, 7};
System.out.println(carAssemblyDP(a, t, e, x));
System.out.println(carAssembly(a, t, e, x));
}
public static int carAssembly(int[][] a, int[][] t, int[] e, int[] x){
int n = a[0].length-1;
return Math.min(carAssemblyRec(a,t, e, x, n, 0) + x[0],
carAssemblyRec(a,t, e, x, n, 1) + x[1]);
}
public static int carAssemblyRec(int[][] a, int[][] t, int[] e, int[] x, int n, int line){
if(n == 0){
return e[line] + a[line][0];
}
int T0 = Math.min(carAssemblyRec(a, t, e, x, n-1, 0) + a[0][n]
, carAssemblyRec(a, t, e, x, n-1, 1) + t[1][n] + a[0][n]);
int T1 = Math.min(carAssemblyRec(a, t, e, x, n-1, 1) + a[1][n]
, carAssemblyRec(a, t, e, x, n-1, 0) + t[0][n] + a[1][n]);
return Math.min(T0, T1);
}
public static int carAssemblyDP(int[][] a, int[][] t, int[] e, int[] x){
int n = a[0].length;
int[] T1 = new int[n];
int[] T2 = new int[n];
T1[0] = e[0] + a[0][0];
T2[0] = e[1] + a[1][0];
for(int i=1; i<n; i++){
T1[i] = Math.min(T1[i-1]+a[0][i], T2[i-1]+t[1][i]+a[0][i]);
T2[i] = Math.min(T2[i-1]+a[1][i], T1[i-1]+t[0][i]+a[1][i]);
}
return Math.min(T1[n-1]+x[0], T2[n-1]+x[1]);
}
}DP输出为35，这是正确的，但递归版本输出是29，这显然是错误的。
回答 1
Stack Overflow用户
发布于 2014-01-19 04:09:47
我会回答我的问题。
public static int carAssemblyRec(int[][] a, int[][] t, int[] e, int[] x, int n, int line){
if(n == 0){
return e[line] + a[line][0];
}
int T0 = Integer.MAX_VALUE;
int T1 = Integer.MAX_VALUE;
if(line == 0){
T0 = Math.min(carAssemblyRec(a, t, e, x, n-1, 0) + a[0][n],
carAssemblyRec(a, t, e, x, n-1, 1) + t[1][n] + a[0][n]);
}else if(line == 1){
T1 = Math.min(carAssemblyRec(a, t, e, x, n-1, 1) + a[1][n],
carAssemblyRec(a, t, e, x, n-1, 0) + t[0][n] + a[1][n]);
}
return Math.min(T0, T1);
} https://stackoverflow.com/questions/20830145
复制相似问题
腾讯云开发者
