PROGRAM DYNAMIC
      IMPLICIT INTEGER(A-Z)
      DOUBLE PRECISION TIMEA,TIMEB,TIMTOT,A(30,30),U(3500000),SUM,TEMP
      INTEGER V(3500000),S(30),SCOMP(30),IPERM(30)
C
C #####################################################################
C                    DYNAMIC PROGRAMMING ALGORITHM
C  OBJECTIVE: MAXIMIZE THE SUM OF THE PROXIMITIES IN THE UPPER TRIANGLE
C             OF THE MATRIX - DOMINANCE INDEX
C #####################################################################
C
      OPEN(1,FILE='ASYM.DAT')
      OPEN(2,FILE='ASYM.OUT')
      READ(1,*) N                              ! Read number of objects
      READ(1,*) ((A(I,J),J=1,N),I=1,N)         ! Read proximity matrix
      CALL GETTIM (IHR, IMIN, ISEC, I100)
      CALL GETDAT (IYR, IMON, IDAY)
      TIMEA=DFLOAT(86400*IDAY+3600*IHR+60*IMIN+ISEC)+DFLOAT(I100)/100.
C
      NSUM = 2**N - 1
      DO I = 1,NSUM
        U(I) = -9.9D+12
      END DO
      DO I = 1,N
        INDEX = 2**(I-1)
        SUM = 0.0D0
        DO J = 1,N
          IF(I.NE.J) SUM = SUM + A(I,J)
        END DO
        V(INDEX) = I
        U(INDEX) = SUM
      END DO
C
      MTC = 0
      DO 70 K = 1,N-1
        NFIRST = 0
        IF(MTC.EQ.0) THEN
          M2 = 0
          DO J = 1,K
            S(J) = M2 + J
          END DO
          IF(S(1).NE.N-K+1) MTC = 1
        END IF
 
 75     IF(MTC.EQ.0) GO TO 70
        IF(NFIRST.EQ.1) THEN
          IF(M2.LT.N-NH) NH = 0
          NH = NH + 1
          M2 = S(K+1-NH)
          DO J = 1,NH
            S(K+J-NH) = M2 + J
          END DO
          MTC = 1
          IF(S(1).EQ.N-K+1) MTC = 0
        END IF
        IF(NFIRST.EQ.0) NFIRST = 1
        INDEX = 0
        DO I = 1,K
          INDEX = INDEX + 2**(S(I)-1)
        END DO 
C      
        JJ = 1
        DO I = 1,N
          SCOMP(I) = 0
        END DO
        IDX = 0
        DO 76 I = 1,N
          DO J = 1,K
            IF(I.EQ.S(J)) GO TO 76
          END DO
          IDX = IDX + 1
          SCOMP(IDX) = I
 76     CONTINUE
C
        NK = N - K
        DO JJ = 1,NK
          J1 = SCOMP(JJ)
          SUM = 0.0D0
          DO I = 1,NK
            I1 = SCOMP(I)
            IF(I1.NE.J1) SUM = SUM + A(J1,I1)
          END DO
          TEMP = U(INDEX) + SUM
          IDXTMP = INDEX + 2**(J1-1)
          IF(TEMP.GT.U(IDXTMP)) THEN
            U(IDXTMP) = TEMP
            V(IDXTMP) = J1
          END IF
        END DO
        GO TO 75
  70  CONTINUE
C
      IPERM(N) = V(NSUM)
      INDEX = NSUM
      LASTIN = IPERM(N)
      DO I = 1,N-1
        INDEX = INDEX - (2**(LASTIN-1))
        LASTIN = V(INDEX)
        IPERM(N-I) = LASTIN
      END DO
C
      CALL GETTIM (IHR, IMIN, ISEC, I100)
      CALL GETDAT (IYR, IMON, IDAY)
      TIMEB=DFLOAT(86400*IDAY+3600*IHR+60*IMIN+ISEC)+DFLOAT(I100)/100.
      TIMTOT = TIMEB - TIMEA
      WRITE(*,80) U(NSUM)
      WRITE(*,81) TIMTOT
      WRITE(*,82) (IPERM(I),I=1,N)
      WRITE(2,80) U(NSUM)
      WRITE(2,81) TIMTOT
      WRITE(2,82) (IPERM(I),I=1,N)
 80   FORMAT(' OPTIMAL DOMINANCE INDEX  ',F15.5)
 81   FORMAT(' TOTAL CPU TIME (SECONDS) ',7X,F8.2)
 82   FORMAT(30I3)
      END