path: root/test/monniaux/glpk-4.65/src/misc/mt1.c

/* mt1.c (0-1 knapsack problem; Martello & Toth algorithm) */

/***********************************************************************
*  This code is part of GLPK (GNU Linear Programming Kit).
*
*  THIS CODE IS THE RESULT OF TRANSLATION OF THE FORTRAN SUBROUTINES
*  MT1 FROM THE BOOK:
*
*  SILVANO MARTELLO, PAOLO TOTH. KNAPSACK PROBLEMS: ALGORITHMS AND
*  COMPUTER IMPLEMENTATIONS. JOHN WILEY & SONS, 1990.
*
*  THE TRANSLATION HAS BEEN DONE WITH THE PERMISSION OF THE AUTHORS OF
*  THE ORIGINAL FORTRAN SUBROUTINES: SILVANO MARTELLO AND PAOLO TOTH.
*
*  The translation was made by Andrew Makhorin <mao@gnu.org>.
*
*  GLPK is free software: you can redistribute it and/or modify it
*  under the terms of the GNU General Public License as published by
*  the Free Software Foundation, either version 3 of the License, or
*  (at your option) any later version.
*
*  GLPK is distributed in the hope that it will be useful, but WITHOUT
*  ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
*  or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
*  License for more details.
*
*  You should have received a copy of the GNU General Public License
*  along with GLPK. If not, see <http://www.gnu.org/licenses/>.
***********************************************************************/

#line 1 ""
/*  -- translated by f2c (version 20100827).
   You must link the resulting object file with libf2c:
	on Microsoft Windows system, link with libf2c.lib;
	on Linux or Unix systems, link with .../path/to/libf2c.a -lm
	or, if you install libf2c.a in a standard place, with -lf2c -lm
	-- in that order, at the end of the command line, as in
		cc *.o -lf2c -lm
	Source for libf2c is in /netlib/f2c/libf2c.zip, e.g.,

		http://www.netlib.org/f2c/libf2c.zip
*/

#if 0 /* by mao */
#include "f2c.h"
#else
#include "env.h"
#include "mt1.h"

typedef int integer;
typedef float real;
#endif

#line 1 ""
/*<       SUBROUTINE MT1(N,P,W,C,Z,X,JDIM,JCK,XX,MIN,PSIGN,WSIGN,ZSIGN) >*/
#if 1 /* by mao */
static int chmt1_(int *, int *, int *, int *, int *, int *);

static
#endif
/* Subroutine */ int mt1_(integer *n, integer *p, integer *w, integer *c__,
	integer *z__, integer *x, integer *jdim, integer *jck, integer *xx,
	integer *min__, integer *psign, integer *wsign, integer *zsign)
{
    /* System generated locals */
    integer i__1;

    /* Local variables */
    static real a, b;
    static integer j, r__, t, j1, n1, ch, ii, jj, kk, in, ll, ip, nn, iu, ii1,
	     chs, lim, lim1, diff, lold, mink;
    extern /* Subroutine */ int chmt1_(integer *, integer *, integer *,
	    integer *, integer *, integer *);
    static integer profit;


/* THIS SUBROUTINE SOLVES THE 0-1 SINGLE KNAPSACK PROBLEM */

/* MAXIMIZE  Z = P(1)*X(1) + ... + P(N)*X(N) */

/* SUBJECT TO:   W(1)*X(1) + ... + W(N)*X(N) .LE. C , */
/*               X(J) = 0 OR 1  FOR J=1,...,N. */

/* THE PROGRAM IS INCLUDED IN THE VOLUME */
/*   S. MARTELLO, P. TOTH, "KNAPSACK PROBLEMS: ALGORITHMS */
/*   AND COMPUTER IMPLEMENTATIONS", JOHN WILEY, 1990 */
/* AND IMPLEMENTS THE BRANCH-AND-BOUND ALGORITHM DESCRIBED IN */
/* SECTION  2.5.2 . */
/* THE PROGRAM DERIVES FROM AN EARLIER CODE PRESENTED IN */
/*  S. MARTELLO, P. TOTH, "ALGORITHM FOR THE SOLUTION OF THE 0-1 SINGLE */
/*  KNAPSACK PROBLEM", COMPUTING, 1978. */

/* THE INPUT PROBLEM MUST SATISFY THE CONDITIONS */

/*   1) 2 .LE. N .LE. JDIM - 1 ; */
/*   2) P(J), W(J), C  POSITIVE INTEGERS; */
/*   3) MAX (W(J)) .LE. C ; */
/*   4) W(1) + ... + W(N) .GT. C ; */
/*   5) P(J)/W(J) .GE. P(J+1)/W(J+1) FOR J=1,...,N-1. */

/* MT1 CALLS  1  PROCEDURE: CHMT1. */

/* THE PROGRAM IS COMPLETELY SELF-CONTAINED AND COMMUNICATION TO IT IS */
/* ACHIEVED SOLELY THROUGH THE PARAMETER LIST OF MT1. */
/* NO MACHINE-DEPENDENT CONSTANT IS USED. */
/* THE PROGRAM IS WRITTEN IN 1967 AMERICAN NATIONAL STANDARD FORTRAN */
/* AND IS ACCEPTED BY THE PFORT VERIFIER (PFORT IS THE PORTABLE */
/* SUBSET OF ANSI DEFINED BY THE ASSOCIATION FOR COMPUTING MACHINERY). */
/* THE PROGRAM HAS BEEN TESTED ON A DIGITAL VAX 11/780 AND AN H.P. */
/* 9000/840. */

/* MT1 NEEDS  8  ARRAYS ( P ,  W ,  X ,  XX ,  MIN ,  PSIGN ,  WSIGN */
/*                        AND  ZSIGN ) OF LENGTH AT LEAST  N + 1 . */

/* MEANING OF THE INPUT PARAMETERS: */
/* N    = NUMBER OF ITEMS; */
/* P(J) = PROFIT OF ITEM  J  (J=1,...,N); */
/* W(J) = WEIGHT OF ITEM  J  (J=1,...,N); */
/* C    = CAPACITY OF THE KNAPSACK; */
/* JDIM = DIMENSION OF THE 8 ARRAYS; */
/* JCK  = 1 IF CHECK ON THE INPUT DATA IS DESIRED, */
/*      = 0 OTHERWISE. */

/* MEANING OF THE OUTPUT PARAMETERS: */
/* Z    = VALUE OF THE OPTIMAL SOLUTION IF  Z .GT. 0 , */
/*      = ERROR IN THE INPUT DATA (WHEN JCK=1) IF Z .LT. 0 : CONDI- */
/*        TION  - Z  IS VIOLATED; */
/* X(J) = 1 IF ITEM  J  IS IN THE OPTIMAL SOLUTION, */
/*      = 0 OTHERWISE. */

/* ARRAYS XX, MIN, PSIGN, WSIGN AND ZSIGN ARE DUMMY. */

/* ALL THE PARAMETERS ARE INTEGER. ON RETURN OF MT1 ALL THE INPUT */
/* PARAMETERS ARE UNCHANGED. */

/*<       INTEGER P(JDIM),W(JDIM),X(JDIM),C,Z >*/
/*<       INTEGER XX(JDIM),MIN(JDIM),PSIGN(JDIM),WSIGN(JDIM),ZSIGN(JDIM) >*/
/*<       INTEGER CH,CHS,DIFF,PROFIT,R,T >*/
/*<       Z = 0 >*/
#line 65 ""
    /* Parameter adjustments */
#line 65 ""
    --zsign;
#line 65 ""
    --wsign;
#line 65 ""
    --psign;
#line 65 ""
    --min__;
#line 65 ""
    --xx;
#line 65 ""
    --x;
#line 65 ""
    --w;
#line 65 ""
    --p;
#line 65 ""

#line 65 ""
    /* Function Body */
#line 65 ""
    *z__ = 0;
/*<       IF ( JCK .EQ. 1 ) CALL CHMT1(N,P,W,C,Z,JDIM) >*/
#line 66 ""
    if (*jck == 1) {
#line 66 ""
	chmt1_(n, &p[1], &w[1], c__, z__, jdim);
#line 66 ""
    }
/*<       IF ( Z .LT. 0 ) RETURN >*/
#line 67 ""
    if (*z__ < 0) {
#line 67 ""
	return 0;
#line 67 ""
    }
/* INITIALIZE. */
/*<       CH = C >*/
#line 69 ""
    ch = *c__;
/*<       IP = 0 >*/
#line 70 ""
    ip = 0;
/*<       CHS = CH >*/
#line 71 ""
    chs = ch;
/*<       DO 10 LL=1,N >*/
#line 72 ""
    i__1 = *n;
#line 72 ""
    for (ll = 1; ll <= i__1; ++ll) {
/*<         IF ( W(LL) .GT. CHS ) GO TO 20 >*/
#line 73 ""
	if (w[ll] > chs) {
#line 73 ""
	    goto L20;
#line 73 ""
	}
/*<         IP = IP + P(LL) >*/
#line 74 ""
	ip += p[ll];
/*<         CHS = CHS - W(LL) >*/
#line 75 ""
	chs -= w[ll];
/*<    10 CONTINUE >*/
#line 76 ""
/* L10: */
#line 76 ""
    }
/*<    20 LL = LL - 1 >*/
#line 77 ""
L20:
#line 77 ""
    --ll;
/*<       IF ( CHS .EQ. 0 ) GO TO 50 >*/
#line 78 ""
    if (chs == 0) {
#line 78 ""
	goto L50;
#line 78 ""
    }
/*<       P(N+1) = 0 >*/
#line 79 ""
    p[*n + 1] = 0;
/*<       W(N+1) = CH + 1 >*/
#line 80 ""
    w[*n + 1] = ch + 1;
/*<       LIM = IP + CHS*P(LL+2)/W(LL+2) >*/
#line 81 ""
    lim = ip + chs * p[ll + 2] / w[ll + 2];
/*<       A = W(LL+1) - CHS >*/
#line 82 ""
    a = (real) (w[ll + 1] - chs);
/*<       B = IP + P(LL+1) >*/
#line 83 ""
    b = (real) (ip + p[ll + 1]);
/*<       LIM1 = B - A*FLOAT(P(LL))/FLOAT(W(LL)) >*/
#line 84 ""
    lim1 = b - a * (real) p[ll] / (real) w[ll];
/*<       IF ( LIM1 .GT. LIM ) LIM = LIM1 >*/
#line 85 ""
    if (lim1 > lim) {
#line 85 ""
	lim = lim1;
#line 85 ""
    }
/*<       MINK = CH + 1 >*/
#line 86 ""
    mink = ch + 1;
/*<       MIN(N) = MINK >*/
#line 87 ""
    min__[*n] = mink;
/*<       DO 30 J=2,N >*/
#line 88 ""
    i__1 = *n;
#line 88 ""
    for (j = 2; j <= i__1; ++j) {
/*<         KK = N + 2 - J >*/
#line 89 ""
	kk = *n + 2 - j;
/*<         IF ( W(KK) .LT. MINK ) MINK = W(KK) >*/
#line 90 ""
	if (w[kk] < mink) {
#line 90 ""
	    mink = w[kk];
#line 90 ""
	}
/*<         MIN(KK-1) = MINK >*/
#line 91 ""
	min__[kk - 1] = mink;
/*<    30 CONTINUE >*/
#line 92 ""
/* L30: */
#line 92 ""
    }
/*<       DO 40 J=1,N >*/
#line 93 ""
    i__1 = *n;
#line 93 ""
    for (j = 1; j <= i__1; ++j) {
/*<         XX(J) = 0 >*/
#line 94 ""
	xx[j] = 0;
/*<    40 CONTINUE >*/
#line 95 ""
/* L40: */
#line 95 ""
    }
/*<       Z = 0 >*/
#line 96 ""
    *z__ = 0;
/*<       PROFIT = 0 >*/
#line 97 ""
    profit = 0;
/*<       LOLD = N >*/
#line 98 ""
    lold = *n;
/*<       II = 1 >*/
#line 99 ""
    ii = 1;
/*<       GO TO 170 >*/
#line 100 ""
    goto L170;
/*<    50 Z = IP >*/
#line 101 ""
L50:
#line 101 ""
    *z__ = ip;
/*<       DO 60 J=1,LL >*/
#line 102 ""
    i__1 = ll;
#line 102 ""
    for (j = 1; j <= i__1; ++j) {
/*<         X(J) = 1 >*/
#line 103 ""
	x[j] = 1;
/*<    60 CONTINUE >*/
#line 104 ""
/* L60: */
#line 104 ""
    }
/*<       NN = LL + 1 >*/
#line 105 ""
    nn = ll + 1;
/*<       DO 70 J=NN,N >*/
#line 106 ""
    i__1 = *n;
#line 106 ""
    for (j = nn; j <= i__1; ++j) {
/*<         X(J) = 0 >*/
#line 107 ""
	x[j] = 0;
/*<    70 CONTINUE >*/
#line 108 ""
/* L70: */
#line 108 ""
    }
/*<       RETURN >*/
#line 109 ""
    return 0;
/* TRY TO INSERT THE II-TH ITEM INTO THE CURRENT SOLUTION. */
/*<    80 IF ( W(II) .LE. CH ) GO TO 90 >*/
#line 111 ""
L80:
#line 111 ""
    if (w[ii] <= ch) {
#line 111 ""
	goto L90;
#line 111 ""
    }
/*<       II1 = II + 1 >*/
#line 112 ""
    ii1 = ii + 1;
/*<       IF ( Z .GE. CH*P(II1)/W(II1) + PROFIT ) GO TO 280 >*/
#line 113 ""
    if (*z__ >= ch * p[ii1] / w[ii1] + profit) {
#line 113 ""
	goto L280;
#line 113 ""
    }
/*<       II = II1 >*/
#line 114 ""
    ii = ii1;
/*<       GO TO 80 >*/
#line 115 ""
    goto L80;
/* BUILD A NEW CURRENT SOLUTION. */
/*<    90 IP = PSIGN(II) >*/
#line 117 ""
L90:
#line 117 ""
    ip = psign[ii];
/*<       CHS = CH - WSIGN(II) >*/
#line 118 ""
    chs = ch - wsign[ii];
/*<       IN = ZSIGN(II) >*/
#line 119 ""
    in = zsign[ii];
/*<       DO 100 LL=IN,N >*/
#line 120 ""
    i__1 = *n;
#line 120 ""
    for (ll = in; ll <= i__1; ++ll) {
/*<         IF ( W(LL) .GT. CHS ) GO TO 160 >*/
#line 121 ""
	if (w[ll] > chs) {
#line 121 ""
	    goto L160;
#line 121 ""
	}
/*<         IP = IP + P(LL) >*/
#line 122 ""
	ip += p[ll];
/*<         CHS = CHS - W(LL) >*/
#line 123 ""
	chs -= w[ll];
/*<   100 CONTINUE >*/
#line 124 ""
/* L100: */
#line 124 ""
    }
/*<       LL = N >*/
#line 125 ""
    ll = *n;
/*<   110 IF ( Z .GE. IP + PROFIT ) GO TO 280 >*/
#line 126 ""
L110:
#line 126 ""
    if (*z__ >= ip + profit) {
#line 126 ""
	goto L280;
#line 126 ""
    }
/*<       Z = IP + PROFIT >*/
#line 127 ""
    *z__ = ip + profit;
/*<       NN = II - 1 >*/
#line 128 ""
    nn = ii - 1;
/*<       DO 120 J=1,NN >*/
#line 129 ""
    i__1 = nn;
#line 129 ""
    for (j = 1; j <= i__1; ++j) {
/*<         X(J) = XX(J) >*/
#line 130 ""
	x[j] = xx[j];
/*<   120 CONTINUE >*/
#line 131 ""
/* L120: */
#line 131 ""
    }
/*<       DO 130 J=II,LL >*/
#line 132 ""
    i__1 = ll;
#line 132 ""
    for (j = ii; j <= i__1; ++j) {
/*<         X(J) = 1 >*/
#line 133 ""
	x[j] = 1;
/*<   130 CONTINUE >*/
#line 134 ""
/* L130: */
#line 134 ""
    }
/*<       IF ( LL .EQ. N ) GO TO 150 >*/
#line 135 ""
    if (ll == *n) {
#line 135 ""
	goto L150;
#line 135 ""
    }
/*<       NN = LL + 1 >*/
#line 136 ""
    nn = ll + 1;
/*<       DO 140 J=NN,N >*/
#line 137 ""
    i__1 = *n;
#line 137 ""
    for (j = nn; j <= i__1; ++j) {
/*<         X(J) = 0 >*/
#line 138 ""
	x[j] = 0;
/*<   140 CONTINUE >*/
#line 139 ""
/* L140: */
#line 139 ""
    }
/*<   150 IF ( Z .NE. LIM ) GO TO 280 >*/
#line 140 ""
L150:
#line 140 ""
    if (*z__ != lim) {
#line 140 ""
	goto L280;
#line 140 ""
    }
/*<       RETURN >*/
#line 141 ""
    return 0;
/*<   160 IU = CHS*P(LL)/W(LL) >*/
#line 142 ""
L160:
#line 142 ""
    iu = chs * p[ll] / w[ll];
/*<       LL = LL - 1 >*/
#line 143 ""
    --ll;
/*<       IF ( IU .EQ. 0 ) GO TO 110 >*/
#line 144 ""
    if (iu == 0) {
#line 144 ""
	goto L110;
#line 144 ""
    }
/*<       IF ( Z .GE. PROFIT + IP + IU ) GO TO 280 >*/
#line 145 ""
    if (*z__ >= profit + ip + iu) {
#line 145 ""
	goto L280;
#line 145 ""
    }
/* SAVE THE CURRENT SOLUTION. */
/*<   170 WSIGN(II) = CH - CHS >*/
#line 147 ""
L170:
#line 147 ""
    wsign[ii] = ch - chs;
/*<       PSIGN(II) = IP >*/
#line 148 ""
    psign[ii] = ip;
/*<       ZSIGN(II) = LL + 1 >*/
#line 149 ""
    zsign[ii] = ll + 1;
/*<       XX(II) = 1 >*/
#line 150 ""
    xx[ii] = 1;
/*<       NN = LL - 1 >*/
#line 151 ""
    nn = ll - 1;
/*<       IF ( NN .LT. II) GO TO 190 >*/
#line 152 ""
    if (nn < ii) {
#line 152 ""
	goto L190;
#line 152 ""
    }
/*<       DO 180 J=II,NN >*/
#line 153 ""
    i__1 = nn;
#line 153 ""
    for (j = ii; j <= i__1; ++j) {
/*<         WSIGN(J+1) = WSIGN(J) - W(J) >*/
#line 154 ""
	wsign[j + 1] = wsign[j] - w[j];
/*<         PSIGN(J+1) = PSIGN(J) - P(J) >*/
#line 155 ""
	psign[j + 1] = psign[j] - p[j];
/*<         ZSIGN(J+1) = LL + 1 >*/
#line 156 ""
	zsign[j + 1] = ll + 1;
/*<         XX(J+1) = 1 >*/
#line 157 ""
	xx[j + 1] = 1;
/*<   180 CONTINUE >*/
#line 158 ""
/* L180: */
#line 158 ""
    }
/*<   190 J1 = LL + 1 >*/
#line 159 ""
L190:
#line 159 ""
    j1 = ll + 1;
/*<       DO 200 J=J1,LOLD >*/
#line 160 ""
    i__1 = lold;
#line 160 ""
    for (j = j1; j <= i__1; ++j) {
/*<         WSIGN(J) = 0 >*/
#line 161 ""
	wsign[j] = 0;
/*<         PSIGN(J) = 0 >*/
#line 162 ""
	psign[j] = 0;
/*<         ZSIGN(J) = J >*/
#line 163 ""
	zsign[j] = j;
/*<   200 CONTINUE >*/
#line 164 ""
/* L200: */
#line 164 ""
    }
/*<       LOLD = LL >*/
#line 165 ""
    lold = ll;
/*<       CH = CHS >*/
#line 166 ""
    ch = chs;
/*<       PROFIT = PROFIT + IP >*/
#line 167 ""
    profit += ip;
/*<       IF ( LL - (N - 2) ) 240, 220, 210 >*/
#line 168 ""
    if ((i__1 = ll - (*n - 2)) < 0) {
#line 168 ""
	goto L240;
#line 168 ""
    } else if (i__1 == 0) {
#line 168 ""
	goto L220;
#line 168 ""
    } else {
#line 168 ""
	goto L210;
#line 168 ""
    }
/*<   210 II = N >*/
#line 169 ""
L210:
#line 169 ""
    ii = *n;
/*<       GO TO 250 >*/
#line 170 ""
    goto L250;
/*<   220 IF ( CH .LT. W(N) ) GO TO 230 >*/
#line 171 ""
L220:
#line 171 ""
    if (ch < w[*n]) {
#line 171 ""
	goto L230;
#line 171 ""
    }
/*<       CH = CH - W(N) >*/
#line 172 ""
    ch -= w[*n];
/*<       PROFIT = PROFIT + P(N) >*/
#line 173 ""
    profit += p[*n];
/*<       XX(N) = 1 >*/
#line 174 ""
    xx[*n] = 1;
/*<   230 II = N - 1 >*/
#line 175 ""
L230:
#line 175 ""
    ii = *n - 1;
/*<       GO TO 250 >*/
#line 176 ""
    goto L250;
/*<   240 II = LL + 2 >*/
#line 177 ""
L240:
#line 177 ""
    ii = ll + 2;
/*<       IF ( CH .GE. MIN(II-1) ) GO TO 80 >*/
#line 178 ""
    if (ch >= min__[ii - 1]) {
#line 178 ""
	goto L80;
#line 178 ""
    }
/* SAVE THE CURRENT OPTIMAL SOLUTION. */
/*<   250 IF ( Z .GE. PROFIT ) GO TO 270 >*/
#line 180 ""
L250:
#line 180 ""
    if (*z__ >= profit) {
#line 180 ""
	goto L270;
#line 180 ""
    }
/*<       Z = PROFIT >*/
#line 181 ""
    *z__ = profit;
/*<       DO 260 J=1,N >*/
#line 182 ""
    i__1 = *n;
#line 182 ""
    for (j = 1; j <= i__1; ++j) {
/*<         X(J) = XX(J) >*/
#line 183 ""
	x[j] = xx[j];
/*<   260 CONTINUE >*/
#line 184 ""
/* L260: */
#line 184 ""
    }
/*<       IF ( Z .EQ. LIM ) RETURN >*/
#line 185 ""
    if (*z__ == lim) {
#line 185 ""
	return 0;
#line 185 ""
    }
/*<   270 IF ( XX(N) .EQ. 0 ) GO TO 280 >*/
#line 186 ""
L270:
#line 186 ""
    if (xx[*n] == 0) {
#line 186 ""
	goto L280;
#line 186 ""
    }
/*<       XX(N) = 0 >*/
#line 187 ""
    xx[*n] = 0;
/*<       CH = CH + W(N) >*/
#line 188 ""
    ch += w[*n];
/*<       PROFIT = PROFIT - P(N) >*/
#line 189 ""
    profit -= p[*n];
/* BACKTRACK. */
/*<   280 NN = II - 1 >*/
#line 191 ""
L280:
#line 191 ""
    nn = ii - 1;
/*<       IF ( NN .EQ. 0 ) RETURN >*/
#line 192 ""
    if (nn == 0) {
#line 192 ""
	return 0;
#line 192 ""
    }
/*<       DO 290 J=1,NN >*/
#line 193 ""
    i__1 = nn;
#line 193 ""
    for (j = 1; j <= i__1; ++j) {
/*<         KK = II - J >*/
#line 194 ""
	kk = ii - j;
/*<         IF ( XX(KK) .EQ. 1 ) GO TO 300 >*/
#line 195 ""
	if (xx[kk] == 1) {
#line 195 ""
	    goto L300;
#line 195 ""
	}
/*<   290 CONTINUE >*/
#line 196 ""
/* L290: */
#line 196 ""
    }
/*<       RETURN >*/
#line 197 ""
    return 0;
/*<   300 R = CH >*/
#line 198 ""
L300:
#line 198 ""
    r__ = ch;
/*<       CH = CH + W(KK) >*/
#line 199 ""
    ch += w[kk];
/*<       PROFIT = PROFIT - P(KK) >*/
#line 200 ""
    profit -= p[kk];
/*<       XX(KK) = 0 >*/
#line 201 ""
    xx[kk] = 0;
/*<       IF ( R .LT. MIN(KK) ) GO TO 310 >*/
#line 202 ""
    if (r__ < min__[kk]) {
#line 202 ""
	goto L310;
#line 202 ""
    }
/*<       II = KK + 1 >*/
#line 203 ""
    ii = kk + 1;
/*<       GO TO 80 >*/
#line 204 ""
    goto L80;
/*<   310 NN = KK + 1 >*/
#line 205 ""
L310:
#line 205 ""
    nn = kk + 1;
/*<       II = KK >*/
#line 206 ""
    ii = kk;
/* TRY TO SUBSTITUTE THE NN-TH ITEM FOR THE KK-TH. */
/*<   320 IF ( Z .GE. PROFIT + CH*P(NN)/W(NN) ) GO TO 280 >*/
#line 208 ""
L320:
#line 208 ""
    if (*z__ >= profit + ch * p[nn] / w[nn]) {
#line 208 ""
	goto L280;
#line 208 ""
    }
/*<       DIFF = W(NN) - W(KK) >*/
#line 209 ""
    diff = w[nn] - w[kk];
/*<       IF ( DIFF ) 370, 330, 340 >*/
#line 210 ""
    if (diff < 0) {
#line 210 ""
	goto L370;
#line 210 ""
    } else if (diff == 0) {
#line 210 ""
	goto L330;
#line 210 ""
    } else {
#line 210 ""
	goto L340;
#line 210 ""
    }
/*<   330 NN = NN + 1 >*/
#line 211 ""
L330:
#line 211 ""
    ++nn;
/*<       GO TO 320 >*/
#line 212 ""
    goto L320;
/*<   340 IF ( DIFF .GT. R ) GO TO 330 >*/
#line 213 ""
L340:
#line 213 ""
    if (diff > r__) {
#line 213 ""
	goto L330;
#line 213 ""
    }
/*<       IF ( Z .GE. PROFIT + P(NN) ) GO TO 330 >*/
#line 214 ""
    if (*z__ >= profit + p[nn]) {
#line 214 ""
	goto L330;
#line 214 ""
    }
/*<       Z = PROFIT + P(NN) >*/
#line 215 ""
    *z__ = profit + p[nn];
/*<       DO 350 J=1,KK >*/
#line 216 ""
    i__1 = kk;
#line 216 ""
    for (j = 1; j <= i__1; ++j) {
/*<         X(J) = XX(J) >*/
#line 217 ""
	x[j] = xx[j];
/*<   350 CONTINUE >*/
#line 218 ""
/* L350: */
#line 218 ""
    }
/*<       JJ = KK + 1 >*/
#line 219 ""
    jj = kk + 1;
/*<       DO 360 J=JJ,N >*/
#line 220 ""
    i__1 = *n;
#line 220 ""
    for (j = jj; j <= i__1; ++j) {
/*<         X(J) = 0 >*/
#line 221 ""
	x[j] = 0;
/*<   360 CONTINUE >*/
#line 222 ""
/* L360: */
#line 222 ""
    }
/*<       X(NN) = 1 >*/
#line 223 ""
    x[nn] = 1;
/*<       IF ( Z .EQ. LIM ) RETURN >*/
#line 224 ""
    if (*z__ == lim) {
#line 224 ""
	return 0;
#line 224 ""
    }
/*<       R = R - DIFF >*/
#line 225 ""
    r__ -= diff;
/*<       KK = NN >*/
#line 226 ""
    kk = nn;
/*<       NN = NN + 1 >*/
#line 227 ""
    ++nn;
/*<       GO TO 320 >*/
#line 228 ""
    goto L320;
/*<   370 T = R - DIFF >*/
#line 229 ""
L370:
#line 229 ""
    t = r__ - diff;
/*<       IF ( T .LT. MIN(NN) ) GO TO 330 >*/
#line 230 ""
    if (t < min__[nn]) {
#line 230 ""
	goto L330;
#line 230 ""
    }
/*<       IF ( Z .GE. PROFIT + P(NN) + T*P(NN+1)/W(NN+1)) GO TO 280 >*/
#line 231 ""
    if (*z__ >= profit + p[nn] + t * p[nn + 1] / w[nn + 1]) {
#line 231 ""
	goto L280;
#line 231 ""
    }
/*<       CH = CH - W(NN) >*/
#line 232 ""
    ch -= w[nn];
/*<       PROFIT = PROFIT + P(NN) >*/
#line 233 ""
    profit += p[nn];
/*<       XX(NN) = 1 >*/
#line 234 ""
    xx[nn] = 1;
/*<       II = NN + 1 >*/
#line 235 ""
    ii = nn + 1;
/*<       WSIGN(NN) = W(NN) >*/
#line 236 ""
    wsign[nn] = w[nn];
/*<       PSIGN(NN) = P(NN) >*/
#line 237 ""
    psign[nn] = p[nn];
/*<       ZSIGN(NN) = II >*/
#line 238 ""
    zsign[nn] = ii;
/*<       N1 = NN + 1 >*/
#line 239 ""
    n1 = nn + 1;
/*<       DO 380 J=N1,LOLD >*/
#line 240 ""
    i__1 = lold;
#line 240 ""
    for (j = n1; j <= i__1; ++j) {
/*<         WSIGN(J) = 0 >*/
#line 241 ""
	wsign[j] = 0;
/*<         PSIGN(J) = 0 >*/
#line 242 ""
	psign[j] = 0;
/*<         ZSIGN(J) = J >*/
#line 243 ""
	zsign[j] = j;
/*<   380 CONTINUE >*/
#line 244 ""
/* L380: */
#line 244 ""
    }
/*<       LOLD = NN >*/
#line 245 ""
    lold = nn;
/*<       GO TO 80 >*/
#line 246 ""
    goto L80;
/*<       END >*/
} /* mt1_ */

/*<       SUBROUTINE CHMT1(N,P,W,C,Z,JDIM) >*/
#if 1 /* by mao */
static
#endif
/* Subroutine */ int chmt1_(integer *n, integer *p, integer *w, integer *c__,
	integer *z__, integer *jdim)
{
    /* System generated locals */
    integer i__1;

    /* Local variables */
    static integer j;
    static real r__, rr;
    static integer jsw;


/* CHECK THE INPUT DATA. */

/*<       INTEGER P(JDIM),W(JDIM),C,Z >*/
/*<       IF ( N .GE. 2 .AND. N .LE. JDIM - 1 ) GO TO 10 >*/
#line 253 ""
    /* Parameter adjustments */
#line 253 ""
    --w;
#line 253 ""
    --p;
#line 253 ""

#line 253 ""
    /* Function Body */
#line 253 ""
    if (*n >= 2 && *n <= *jdim - 1) {
#line 253 ""
	goto L10;
#line 253 ""
    }
/*<       Z = - 1 >*/
#line 254 ""
    *z__ = -1;
/*<       RETURN >*/
#line 255 ""
    return 0;
/*<    10 IF ( C .GT. 0 ) GO TO 30 >*/
#line 256 ""
L10:
#line 256 ""
    if (*c__ > 0) {
#line 256 ""
	goto L30;
#line 256 ""
    }
/*<    20 Z = - 2 >*/
#line 257 ""
L20:
#line 257 ""
    *z__ = -2;
/*<       RETURN >*/
#line 258 ""
    return 0;
/*<    30 JSW = 0 >*/
#line 259 ""
L30:
#line 259 ""
    jsw = 0;
/*<       RR = FLOAT(P(1))/FLOAT(W(1)) >*/
#line 260 ""
    rr = (real) p[1] / (real) w[1];
/*<       DO 50 J=1,N >*/
#line 261 ""
    i__1 = *n;
#line 261 ""
    for (j = 1; j <= i__1; ++j) {
/*<         R = RR >*/
#line 262 ""
	r__ = rr;
/*<         IF ( P(J) .LE. 0 ) GO TO 20 >*/
#line 263 ""
	if (p[j] <= 0) {
#line 263 ""
	    goto L20;
#line 263 ""
	}
/*<         IF ( W(J) .LE. 0 ) GO TO 20 >*/
#line 264 ""
	if (w[j] <= 0) {
#line 264 ""
	    goto L20;
#line 264 ""
	}
/*<         JSW = JSW + W(J) >*/
#line 265 ""
	jsw += w[j];
/*<         IF ( W(J) .LE. C ) GO TO 40 >*/
#line 266 ""
	if (w[j] <= *c__) {
#line 266 ""
	    goto L40;
#line 266 ""
	}
/*<         Z = - 3 >*/
#line 267 ""
	*z__ = -3;
/*<         RETURN >*/
#line 268 ""
	return 0;
/*<    40   RR = FLOAT(P(J))/FLOAT(W(J)) >*/
#line 269 ""
L40:
#line 269 ""
	rr = (real) p[j] / (real) w[j];
/*<         IF ( RR .LE. R ) GO TO 50 >*/
#line 270 ""
	if (rr <= r__) {
#line 270 ""
	    goto L50;
#line 270 ""
	}
/*<         Z = - 5 >*/
#line 271 ""
	*z__ = -5;
/*<         RETURN >*/
#line 272 ""
	return 0;
/*<    50 CONTINUE >*/
#line 273 ""
L50:
#line 273 ""
	;
#line 273 ""
    }
/*<       IF ( JSW .GT. C ) RETURN >*/
#line 274 ""
    if (jsw > *c__) {
#line 274 ""
	return 0;
#line 274 ""
    }
/*<       Z = - 4 >*/
#line 275 ""
    *z__ = -4;
/*<       RETURN >*/
#line 276 ""
    return 0;
/*<       END >*/
} /* chmt1_ */

#if 1 /* by mao */
int mt1(int n, int p[], int w[], int c, int x[], int jck, int xx[],
      int min[], int psign[], int wsign[], int zsign[])
{     /* solve 0-1 knapsack problem */
      int z, jdim = n+1, j, s1, s2;
      mt1_(&n, &p[1], &w[1], &c, &z, &x[1], &jdim, &jck, &xx[1],
         &min[1], &psign[1], &wsign[1], &zsign[1]);
      /* check solution found */
      s1 = s2 = 0;
      for (j = 1; j <= n; j++)
      {  xassert(x[j] == 0 || x[j] == 1);
         if (x[j])
            s1 += p[j], s2 += w[j];
      }
      xassert(s1 == z);
      xassert(s2 <= c);
      return z;
}
#endif

/* eof */