算法之装配线问题
2013年12月12日
⁄ 综合
⁄ 共 1819字 ⁄ 字号
小 中 大
- package com.eshore.sweetop.dynamicprogramming;
- public class Colonel {
-
-
- int[] a1={7,9,3,4,8,4};
-
- int[] a2={8,5,6,4,5,7};
-
- int[] t1={2,3,1,3,4};
-
- int[] t2={2,1,2,2,1};
-
- int e1=2;
-
- int e2=4;
-
- int x1=3;
-
- int x2=2;
- int[] f1=new int[a1.length];
- int[] f2=new int[a2.length];
- int[] l1=new int[a1.length];
- int[] l2=new int[a2.length];
- int f;
- int l;
-
-
- public void fastestWay(){
- f1[0]=e1+a1[0];
- f2[0]=e2+a2[0];
- l1[0]=1;
- l2[0]=2;
-
- for (int i = 1; i < a1.length; i++) {
- if(f1[i-1]<=f2[i-1]+t2[i-1]){
- f1[i]=f1[i-1]+a1[i];
- l1[i]=1;
- }else{
- f1[i]=f2[i-1]+t2[i-1]+a1[i];
- l1[i]=2;
- }
- if(f2[i-1]<=f1[i-1]+t1[i-1]){
- f2[i]=f2[i-1]+a2[i];
- l2[i]=2;
- }else{
- f2[i]=f1[i-1]+t1[i-1]+a2[i];
- l2[i]=1;
- }
- }
- if(f1[a1.length-1]+x1<=f2[a2.length-1]+x2){
- f=f1[a1.length-1]+x1;
- l=1;
- }else{
- f=f2[a2.length-1]+x2;
- l=2;
- }
- }
-
- public void display(){
- int i=l;
- System.out.println("最短装配线");
- System.out.println("line "+i+", station "+l1.length);
- for (int j = l1.length-1; j > 0; j--) {
- int[] min=null;
- if(i==1){
- min=l1;
- }else{
- min=l2;
- }
- i=min[j];
- System.out.println("line "+i+", station "+j);
- }
- }
-
- public static void main(String[] args) {
- Colonel c=new Colonel();
- c.fastestWay();
- System.out.println("最短时间："+c.f);
- c.display();
- }
- }