diaodu.rar_Algorithm A5 GSM_Java 8_diaodu_动态规划 java

package diaodu; public class dd { public static void main(String[] args) { int sum; int a[]={2,5,7,10,5,2}; int b[]={3,8,4,11,3,4}; int []c=new int[6]; sum=flowShop(a,b,c); // System.out.println(c); System.out.println(sum); } public static int flowShop(int []a,int []b,int c[]) {int n=a.length; Element[]d=new Element[n]; for(int i=0;i<n;i++) { int key=a[i]>b[i]?b[i]:a[i]; boolean job=a[i]<=b[i]; d[i]=new Element(key,i,job); } //System.out.println(d); // MergeSort.mergeSort(d); int j=0,k=n-1; for(int i=0;i<n;i++) { if(d[i].job) c[j++]=d[i].index; else c[k--]=d[i].index; } j=a[c[0]]; k=j+b[c[0]]; for(int i=1;i<n;i++) { j+=a[c[i]]; k=j<k?k+b[c[i]]:j+b[c[i]]; } return k; } public static class Element implements Comparable { int key; int index; boolean job; public Element(int kk,int ii,boolean jj) { key=kk; index=ii; job=jj; } public int compareTo(Object x) { int xkey=((Element)x).key; if(key<xkey) return -1; if(key==xkey) return 0; return 1; } } }