一家汽车厂有两条装配线，每条装配线有n个工位。车站用S表示 i、 j 其中i为1或2，表示工位所在的装配线，j表示工位编号。每个站点所用的时间用a表示 i、 j .每个工位都专门从事发动机装配、车身装配、喷漆等工作。因此，汽车底盘在出厂前必须按顺序通过n个工位。两条装配线的平行工位执行相同的任务。经过S站后 i、 j ，它将继续运行到S站 i、 j+1 除非它决定转到另一条线路。继续在同一条线路上运行不会产生额外费用，但从j–1站的i号线到另一条线路的j站的换乘需要时间t i、 j .每条装配线需要一个进入时间e 我 退出时间x 我 这两条线可能不同。给出一个算法来计算制造汽车底盘所需的最短时间。
null
下图清楚地显示了问题：
可以从问题陈述中提取以下信息，使其更简单：
- 两条装配线，1和2，每个装配线的工位从1到n。
- 汽车底盘必须按顺序（在两条装配线中的任何一条）通过从1到n的所有工位。i、 e.如果它们不在一个移动距离内，则不能从站i跳到站j。
- 汽车底盘可以在同一条线上向前移动一个工位，或在另一条线上对角移动一个工位。从i号线移动到j站会产生额外费用ti，j。在同一条线内移动不会产生任何费用。
- i线j站所用时间为 i、 j .
- s i、 j 代表i线上的站j。
将问题分解为更小的子问题： 如果已知第（i-1）个阶乘，我们可以很容易地找到第i个阶乘。我们可以在这里申请类似的基金吗？ 如果机箱离开站点的最短时间为S i、 j-1 已知离开S站的最短时间 i、 j 可以通过结合 i、 j 和t i、 j . T1（j） 表示汽车底盘离开装配线1上的工位j所需的最短时间。 T2（j） 表示汽车底盘离开装配线2上的工位j所需的最短时间。
基本情况： 进入时间为e 我 只有当汽车底盘进入汽车工厂时才会出现。 从1号线第一站出发所需时间如下： T1（1）=1号线的进入时间+在S站的时间 1,1 T1（1）=e 1. +a 1,1 同样，从2号线第一站出发所需的时间如下： T2（1）=e 2. +a 2,1
递归关系： 如果我们看一下问题陈述，它很快就会归结为以下观察结果： S站的汽车底盘 1，j 可以从S站来 1，j-1 还是S站 2，j-1 .
案例#1：它的前一站是S 1，j-1 离开S站的最短时间 1，j 由以下公式给出： T1（j）=离开S站所需的最短时间 1，j-1 +在S站的时间 1，j T1（j）=T1（j-1）+a 1，j
案例2：它的前一站是S 2，j-1 离开车站S1，j的最短时间如下： T1（j）=离开S站所需的最短时间 2，j-1 +变更装配线产生的额外成本+在S站花费的时间 1，j T1（j）=T2（j-1）+t 2，j +a 1，j
最小时间T1（j）由#1和#2两种情况下获得的最小值给出。 T1（j）=min（T1（j-1）+a 1，j )，（T2（j-1）+t 2，j +a 1，j ))
同样，到达S2站的最短时间j由下式给出： T2（j）=min（T2（j-1）+a 2，j )，（T1（j-1）+t 1，j +a 2，j ))
汽车底盘出厂所需的最短总时间如下所示： Tmin=分钟（离开车站所需的时间） i、 n +（离开汽车工厂所需的时间） Tmin=min（T1（n）+x 1. ，T2（n）+x 2. )
为什么是动态规划？ 上述递归显示了重叠的子问题。有两种方法可以到达S站 1，j :
- 从S站 1，j-1
- 从S站 2，j-1
所以，找到离开S站的最短时间 1，j 必须计算出离开前两个站点的最短时间（如上递归所述）。
同样，到达S站有两种方式 2，j :
- 从S站 2，j-1
- 从S站 1，j-1
请注意，离开车站的最短时间为 1，j-1 和S 2，j-1 已经计算过了。 因此，我们需要两个表来存储装配线中每个工位的部分计算结果。桌子将以自下而上的方式填满。
注： 在这篇文章中，“离开”一词被用来代替“到达”，以避免混淆。由于汽车底盘必须在每个工位停留固定时间，所以“离开”这个词更合适。
实施：
C++
// A C++ program to find minimum possible // time by the car chassis to complete #include <bits/stdc++.h> using namespace std; #define NUM_LINE 2 #define NUM_STATION 4 // Utility function to find a minimum of two numbers int min( int a, int b) { return a < b ? a : b; } int carAssembly( int a[][NUM_STATION], int t[][NUM_STATION], int *e, int *x) { int T1[NUM_STATION], T2[NUM_STATION], i; // time taken to leave first station in line 1 T1[0] = e[0] + a[0][0]; // time taken to leave first station in line 2 T2[0] = e[1] + a[1][0]; // Fill tables T1[] and T2[] using the // above given recursive relations for (i = 1; i < NUM_STATION; ++i) { T1[i] = min(T1[i - 1] + a[0][i], T2[i - 1] + t[1][i] + a[0][i]); T2[i] = min(T2[i - 1] + a[1][i], T1[i - 1] + t[0][i] + a[1][i]); } // Consider exit times and return minimum return min(T1[NUM_STATION - 1] + x[0], T2[NUM_STATION - 1] + x[1]); } // Driver Code int main() { int a[][NUM_STATION] = {{4, 5, 3, 2}, {2, 10, 1, 4}}; int t[][NUM_STATION] = {{0, 7, 4, 5}, {0, 9, 2, 8}}; int e[] = {10, 12}, x[] = {18, 7}; cout << carAssembly(a, t, e, x); return 0; } // This is code is contributed by rathbhupendra |
C
// A C program to find minimum possible time by the car chassis to complete #include <stdio.h> #define NUM_LINE 2 #define NUM_STATION 4 // Utility function to find minimum of two numbers int min( int a, int b) { return a < b ? a : b; } int carAssembly( int a[][NUM_STATION], int t[][NUM_STATION], int *e, int *x) { int T1[NUM_STATION], T2[NUM_STATION], i; T1[0] = e[0] + a[0][0]; // time taken to leave first station in line 1 T2[0] = e[1] + a[1][0]; // time taken to leave first station in line 2 // Fill tables T1[] and T2[] using the above given recursive relations for (i = 1; i < NUM_STATION; ++i) { T1[i] = min(T1[i-1] + a[0][i], T2[i-1] + t[1][i] + a[0][i]); T2[i] = min(T2[i-1] + a[1][i], T1[i-1] + t[0][i] + a[1][i]); } // Consider exit times and return minimum return min(T1[NUM_STATION-1] + x[0], T2[NUM_STATION-1] + x[1]); } int main() { int a[][NUM_STATION] = {{4, 5, 3, 2}, {2, 10, 1, 4}}; int t[][NUM_STATION] = {{0, 7, 4, 5}, {0, 9, 2, 8}}; int e[] = {10, 12}, x[] = {18, 7}; printf ( "%d" , carAssembly(a, t, e, x)); return 0; } |
JAVA
// A java program to find minimum possible // time by the car chassis to complete import java.io.*; class GFG { static int NUM_LINE = 2 ; static int NUM_STATION = 4 ; // Utility function to find minimum of two numbers static int min( int a, int b) { return a < b ? a : b; } static int carAssembly( int a[][], int t[][], int e[], int x[]) { int T1[]= new int [NUM_STATION]; int T2[] = new int [NUM_STATION] ; int i; // time taken to leave first station in line 1 T1[ 0 ] = e[ 0 ] + a[ 0 ][ 0 ]; // time taken to leave first station in line 2 T2[ 0 ] = e[ 1 ] + a[ 1 ][ 0 ]; // Fill tables T1[] and T2[] using // the above given recursive relations for (i = 1 ; i < NUM_STATION; ++i) { T1[i] = min(T1[i - 1 ] + a[ 0 ][i], T2[i - 1 ] + t[ 1 ][i] + a[ 0 ][i]); T2[i] = min(T2[i - 1 ] + a[ 1 ][i], T1[i - 1 ] + t[ 0 ][i] + a[ 1 ][i]); } // Consider exit times and return minimum return min(T1[NUM_STATION- 1 ] + x[ 0 ], T2[NUM_STATION- 1 ] + x[ 1 ]); } // Driver code 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 }, x[] = { 18 , 7 }; System.out.println(carAssembly(a, t, e, x)); } } // This code is contributed by vt_m |
Python3
# Python program to find minimum possible # time by the car chassis to complete def carAssembly (a, t, e, x): NUM_STATION = len (a[ 0 ]) T1 = [ 0 for i in range (NUM_STATION)] T2 = [ 0 for i in range (NUM_STATION)] T1[ 0 ] = e[ 0 ] + a[ 0 ][ 0 ] # time taken to leave # first station in line 1 T2[ 0 ] = e[ 1 ] + a[ 1 ][ 0 ] # time taken to leave # first station in line 2 # Fill tables T1[] and T2[] using # above given recursive relations for i in range ( 1 , NUM_STATION): T1[i] = min (T1[i - 1 ] + a[ 0 ][i], T2[i - 1 ] + t[ 1 ][i] + a[ 0 ][i]) T2[i] = min (T2[i - 1 ] + a[ 1 ][i], T1[i - 1 ] + t[ 0 ][i] + a[ 1 ][i] ) # consider exit times and return minimum return min (T1[NUM_STATION - 1 ] + x[ 0 ], T2[NUM_STATION - 1 ] + x[ 1 ]) a = [[ 4 , 5 , 3 , 2 ], [ 2 , 10 , 1 , 4 ]] t = [[ 0 , 7 , 4 , 5 ], [ 0 , 9 , 2 , 8 ]] e = [ 10 , 12 ] x = [ 18 , 7 ] print (carAssembly(a, t, e, x)) # This code is contributed by Soumen Ghosh |
C#
// A C# program to find minimum possible // time by the car chassis to complete using System; class GFG { static int NUM_STATION = 4; // Utility function to find minimum // of two numbers static int min( int a, int b) { return a < b ? a : b; } static int carAssembly( int [,]a, int [,]t, int []e, int []x) { int []T1= new int [NUM_STATION]; int []T2 = new int [NUM_STATION] ; int i; // time taken to leave first station // in line 1 T1[0] = e[0] + a[0,0]; // time taken to leave first station // in line 2 T2[0] = e[1] + a[1,0]; // Fill tables T1[] and T2[] using // the above given recursive relations for (i = 1; i < NUM_STATION; ++i) { T1[i] = min(T1[i - 1] + a[0,i], T2[i - 1] + t[1,i] + a[0,i]); T2[i] = min(T2[i - 1] + a[1,i], T1[i - 1] + t[0,i] + a[1,i]); } // Consider exit times and return // minimum return min(T1[NUM_STATION-1] + x[0], T2[NUM_STATION-1] + x[1]); } // Driver code public static void Main () { 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}; Console.Write(carAssembly(a, t, e, x)); } } // This code is contributed by nitin mittal. |
PHP
<?php // A PHP program to find minimum // possible time by the car chassis // to complete $NUM_LINE = 2; $NUM_STATION = 4; // Utility function to find // minimum of two numbers function carAssembly( $a , $t , $e , $x ) { global $NUM_LINE , $NUM_STATION ; $T1 = array (); $T2 = array (); $i ; $T1 [0] = $e [0] + $a [0][0]; // time taken to leave // first station in line 1 $T2 [0] = $e [1] + $a [1][0]; // time taken to leave // first station in line 2 // Fill tables T1[] and T2[] // using the above given // recursive relations for ( $i = 1; $i < $NUM_STATION ; ++ $i ) { $T1 [ $i ] = min( $T1 [ $i - 1] + $a [0][ $i ], $T2 [ $i - 1] + $t [1][ $i ] + $a [0][ $i ]); $T2 [ $i ] = min( $T2 [ $i - 1] + $a [1][ $i ], $T1 [ $i - 1] + $t [0][ $i ] + $a [1][ $i ]); } // Consider exit times // and return minimum return min( $T1 [ $NUM_STATION - 1] + $x [0], $T2 [ $NUM_STATION - 1] + $x [1]); } // Driver Code $a = array ( array (4, 5, 3, 2), array (2, 10, 1, 4)); $t = array ( array (0, 7, 4, 5), array (0, 9, 2, 8)); $e = array (10, 12); $x = array (18, 7); echo carAssembly( $a , $t , $e , $x ); // This code is contributed // by anuj_67. ?> |
Javascript
<script> // A JavaScript program to find minimum possible // time by the car chassis to complete const NUM_LINE = 2; const NUM_STATION = 4; // Utility function to find a minimum of two numbers function min(a, b) { return a < b ? a : b; } function carAssembly(a, t, e, x) { let T1 = new Array(NUM_STATION); let T2 = new Array(NUM_STATION); let i; // time taken to leave first station in line 1 T1[0] = e[0] + a[0][0]; // time taken to leave first station in line 2 T2[0] = e[1] + a[1][0]; // Fill tables T1[] and T2[] using the // above given recursive relations for (i = 1; i < NUM_STATION; ++i) { T1[i] = min(T1[i - 1] + a[0][i], T2[i - 1] + t[1][i] + a[0][i]); T2[i] = min(T2[i - 1] + a[1][i], T1[i - 1] + t[0][i] + a[1][i]); } // Consider exit times and return minimum return min(T1[NUM_STATION - 1] + x[0], T2[NUM_STATION - 1] + x[1]); } // Driver Code let a = [[4, 5, 3, 2], [2, 10, 1, 4]]; let t = [[0, 7, 4, 5], [0, 9, 2, 8]]; let e = [10, 12], x = [18, 7]; document.write(carAssembly(a, t, e, x)); // This code is contributed by Surbhi Tyagi. </script> |
输出：
35
粗线显示给定输入值的汽车底盘覆盖的路径。我们只需要辅助数组中的最后两个值。因此，我们可以使用两个变量，而不是创建两个数组。
C++
// A space optimized solution for // assembly line scheduling #include <bits/stdc++.h> using namespace std; int carAssembly( int a[][4], int t[][4], int *e, int *x) { int first, second, i; // Time taken to leave first // station in line 1 first = e[0] + a[0][0]; // Time taken to leave first // station in line 2 second = e[1] + a[1][0]; // Fill tables T1[] and T2[] using the // above given recursive relations for (i = 1; i < 4; ++i) { int up = min(first + a[0][i], second + t[1][i] + a[0][i]); int down = min(second + a[1][i], first + t[0][i] + a[1][i]); first = up; second = down; } // Consider exit times and // return minimum return min(first + x[0], second + x[1]); } // Driver Code int main() { int a[][4] = { { 4, 5, 3, 2 }, { 2, 10, 1, 4 } }; int t[][4] = { { 0, 7, 4, 5 }, { 0, 9, 2, 8 } }; int e[] = { 10, 12 }, x[] = { 18, 7 }; cout << carAssembly(a, t, e, x); return 0; } // This code is contributed by chitrasingla2001 |
JAVA
// A space optimized solution for assembly line scheduling public class AssemblyLine { 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 }, x[] = { 18 , 7 }; System.out.println(carAssembleTime(a, t, e, x)); } public static int carAssembleTime( int a[][], int t[][], int e[], int x[]) { int n = a[ 0 ].length; // time taken to leave first station in line 1 int first = e[ 0 ] + a[ 0 ][ 0 ]; // time taken to leave first station in line 2 int second = e[ 1 ] + a[ 1 ][ 0 ]; for ( int i = 1 ; i < n; i++) { int up = Math.min(first + a[ 0 ][i], second + t[ 1 ][i] + a[ 0 ][i]), down = Math.min(second + a[ 1 ][i], first + t[ 0 ][i] + a[ 1 ][i]); first = up; second = down; } first += x[ 0 ]; second += x[ 1 ]; return Math.min(first, second); } } |
Python3
# A space optimized solution for assembly # line scheduling in Python3 def carAssembleTime(a, t, e, x): n = len (a[ 0 ]) # Time taken to leave first station # in line 1 first = e[ 0 ] + a[ 0 ][ 0 ] # Time taken to leave first station # in line 2 second = e[ 1 ] + a[ 1 ][ 0 ] for i in range ( 1 , n): up = min (first + a[ 0 ][i], second + t[ 1 ][i] + a[ 0 ][i]) down = min (second + a[ 1 ][i], first + t[ 0 ][i] + a[ 1 ][i]) first, second = up, down first + = x[ 0 ] second + = x[ 1 ] return min (first, second) # Driver Code a = [ [ 4 , 5 , 3 , 2 ], [ 2 , 10 , 1 , 4 ] ] t = [ [ 0 , 7 , 4 , 5 ], [ 0 , 9 , 2 , 8 ] ] e = [ 10 , 12 ] x = [ 18 , 7 ] print (carAssembleTime(a, t, e, x)) # This code is contributed by Prateek Gupta |
C#
// A space optimized solution for // assembly line scheduling using System; class GFG{ static int carAssembleTime( int [,] a, int [,] t, int [] e, int [] x) { int n = a.GetLength(1); // Time taken to leave first station in line 1 int first = e[0] + a[0, 0]; // Time taken to leave first station in line 2 int second = e[1] + a[1, 0]; for ( int i = 1; i < n; i++) { int up = Math.Min(first + a[0, i], second + t[1, i] + a[0, i]), down = Math.Min(second + a[1, i], first + t[0, i] + a[1, i]); first = up; second = down; } first += x[0]; second += x[1]; return Math.Min(first, second); } // Driver Code static void Main() { int [,] a = { { 4, 5, 3, 2 }, { 2, 10, 1, 4 } }; int [,] t = { { 0, 7, 4, 5 }, { 0, 9, 2, 8 } }; int [] e = { 10, 12 }, x = { 18, 7 }; Console.WriteLine(carAssembleTime(a, t, e, x)); } } // This code is contributed by divyeshrabadiya07 |
Javascript
<script> // A space optimized solution for assembly line scheduling function carAssembleTime(a , t , e , x) { var n = a[0].length; // time taken to leave first station in line 1 var first = e[0] + a[0][0]; // time taken to leave first station in line 2 var second = e[1] + a[1][0]; for ( var i = 1; i < n; i++) { var up = Math.min(first + a[0][i], second + t[1][i] + a[0][i]), down = Math.min(second + a[1][i], first + t[0][i] + a[1][i]); first = up; second = down; } first += x[0]; second += x[1]; return Math.min(first, second); } var a = [ [ 4, 5, 3, 2 ], [ 2, 10, 1, 4 ] ]; var t = [ [ 0, 7, 4, 5 ], [ 0, 9, 2, 8 ] ]; var e = [ 10, 12 ], x = [ 18, 7 ]; document.write(carAssembleTime(a, t, e, x)); // This code is contributed by gauravrajput1 </script> |
输出：
35
练习： 扩展上述算法以打印工厂中汽车底盘覆盖的路径。
参考资料： 算法导论第三版由Clifford Stein、Thomas H.Cormen、Charles E.Leiserson、Ronald L.Rivest编写 本文由 阿希什·巴恩瓦尔 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
