1 /* mt1.c (0-1 knapsack problem; Martello & Toth algorithm) */
2
3 /***********************************************************************
4 * This code is part of GLPK (GNU Linear Programming Kit).
5 *
6 * THIS CODE IS THE RESULT OF TRANSLATION OF THE FORTRAN SUBROUTINES
7 * MT1 FROM THE BOOK:
8 *
9 * SILVANO MARTELLO, PAOLO TOTH. KNAPSACK PROBLEMS: ALGORITHMS AND
10 * COMPUTER IMPLEMENTATIONS. JOHN WILEY & SONS, 1990.
11 *
12 * THE TRANSLATION HAS BEEN DONE WITH THE PERMISSION OF THE AUTHORS OF
13 * THE ORIGINAL FORTRAN SUBROUTINES: SILVANO MARTELLO AND PAOLO TOTH.
14 *
15 * The translation was made by Andrew Makhorin <mao@gnu.org>.
16 *
17 * GLPK is free software: you can redistribute it and/or modify it
18 * under the terms of the GNU General Public License as published by
19 * the Free Software Foundation, either version 3 of the License, or
20 * (at your option) any later version.
21 *
22 * GLPK is distributed in the hope that it will be useful, but WITHOUT
23 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
24 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
25 * License for more details.
26 *
27 * You should have received a copy of the GNU General Public License
28 * along with GLPK. If not, see <http://www.gnu.org/licenses/>.
29 ***********************************************************************/
30
31 #line 1 ""
32 /* -- translated by f2c (version 20100827).
33 You must link the resulting object file with libf2c:
34 on Microsoft Windows system, link with libf2c.lib;
35 on Linux or Unix systems, link with .../path/to/libf2c.a -lm
36 or, if you install libf2c.a in a standard place, with -lf2c -lm
37 -- in that order, at the end of the command line, as in
38 cc *.o -lf2c -lm
39 Source for libf2c is in /netlib/f2c/libf2c.zip, e.g.,
40
41 http://www.netlib.org/f2c/libf2c.zip
42 */
43
44 #if 0 /* by mao */
45 #include "f2c.h"
46 #else
47 #include "env.h"
48 #include "mt1.h"
49
50 typedef int integer;
51 typedef float real;
52 #endif
53
54 #line 1 ""
55 /*< SUBROUTINE MT1(N,P,W,C,Z,X,JDIM,JCK,XX,MIN,PSIGN,WSIGN,ZSIGN) >*/
56 #if 1 /* by mao */
57 static int chmt1_(int *, int *, int *, int *, int *, int *);
58
59 static
60 #endif
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)61 /* Subroutine */ int mt1_(integer *n, integer *p, integer *w, integer *c__,
62 integer *z__, integer *x, integer *jdim, integer *jck, integer *xx,
63 integer *min__, integer *psign, integer *wsign, integer *zsign)
64 {
65 /* System generated locals */
66 integer i__1;
67
68 /* Local variables */
69 static real a, b;
70 static integer j, r__, t, j1, n1, ch, ii, jj, kk, in, ll, ip, nn, iu, ii1,
71 chs, lim, lim1, diff, lold, mink;
72 extern /* Subroutine */ int chmt1_(integer *, integer *, integer *,
73 integer *, integer *, integer *);
74 static integer profit;
75
76
77 /* THIS SUBROUTINE SOLVES THE 0-1 SINGLE KNAPSACK PROBLEM */
78
79 /* MAXIMIZE Z = P(1)*X(1) + ... + P(N)*X(N) */
80
81 /* SUBJECT TO: W(1)*X(1) + ... + W(N)*X(N) .LE. C , */
82 /* X(J) = 0 OR 1 FOR J=1,...,N. */
83
84 /* THE PROGRAM IS INCLUDED IN THE VOLUME */
85 /* S. MARTELLO, P. TOTH, "KNAPSACK PROBLEMS: ALGORITHMS */
86 /* AND COMPUTER IMPLEMENTATIONS", JOHN WILEY, 1990 */
87 /* AND IMPLEMENTS THE BRANCH-AND-BOUND ALGORITHM DESCRIBED IN */
88 /* SECTION 2.5.2 . */
89 /* THE PROGRAM DERIVES FROM AN EARLIER CODE PRESENTED IN */
90 /* S. MARTELLO, P. TOTH, "ALGORITHM FOR THE SOLUTION OF THE 0-1 SINGLE */
91 /* KNAPSACK PROBLEM", COMPUTING, 1978. */
92
93 /* THE INPUT PROBLEM MUST SATISFY THE CONDITIONS */
94
95 /* 1) 2 .LE. N .LE. JDIM - 1 ; */
96 /* 2) P(J), W(J), C POSITIVE INTEGERS; */
97 /* 3) MAX (W(J)) .LE. C ; */
98 /* 4) W(1) + ... + W(N) .GT. C ; */
99 /* 5) P(J)/W(J) .GE. P(J+1)/W(J+1) FOR J=1,...,N-1. */
100
101 /* MT1 CALLS 1 PROCEDURE: CHMT1. */
102
103 /* THE PROGRAM IS COMPLETELY SELF-CONTAINED AND COMMUNICATION TO IT IS */
104 /* ACHIEVED SOLELY THROUGH THE PARAMETER LIST OF MT1. */
105 /* NO MACHINE-DEPENDENT CONSTANT IS USED. */
106 /* THE PROGRAM IS WRITTEN IN 1967 AMERICAN NATIONAL STANDARD FORTRAN */
107 /* AND IS ACCEPTED BY THE PFORT VERIFIER (PFORT IS THE PORTABLE */
108 /* SUBSET OF ANSI DEFINED BY THE ASSOCIATION FOR COMPUTING MACHINERY). */
109 /* THE PROGRAM HAS BEEN TESTED ON A DIGITAL VAX 11/780 AND AN H.P. */
110 /* 9000/840. */
111
112 /* MT1 NEEDS 8 ARRAYS ( P , W , X , XX , MIN , PSIGN , WSIGN */
113 /* AND ZSIGN ) OF LENGTH AT LEAST N + 1 . */
114
115 /* MEANING OF THE INPUT PARAMETERS: */
116 /* N = NUMBER OF ITEMS; */
117 /* P(J) = PROFIT OF ITEM J (J=1,...,N); */
118 /* W(J) = WEIGHT OF ITEM J (J=1,...,N); */
119 /* C = CAPACITY OF THE KNAPSACK; */
120 /* JDIM = DIMENSION OF THE 8 ARRAYS; */
121 /* JCK = 1 IF CHECK ON THE INPUT DATA IS DESIRED, */
122 /* = 0 OTHERWISE. */
123
124 /* MEANING OF THE OUTPUT PARAMETERS: */
125 /* Z = VALUE OF THE OPTIMAL SOLUTION IF Z .GT. 0 , */
126 /* = ERROR IN THE INPUT DATA (WHEN JCK=1) IF Z .LT. 0 : CONDI- */
127 /* TION - Z IS VIOLATED; */
128 /* X(J) = 1 IF ITEM J IS IN THE OPTIMAL SOLUTION, */
129 /* = 0 OTHERWISE. */
130
131 /* ARRAYS XX, MIN, PSIGN, WSIGN AND ZSIGN ARE DUMMY. */
132
133 /* ALL THE PARAMETERS ARE INTEGER. ON RETURN OF MT1 ALL THE INPUT */
134 /* PARAMETERS ARE UNCHANGED. */
135
136 /*< INTEGER P(JDIM),W(JDIM),X(JDIM),C,Z >*/
137 /*< INTEGER XX(JDIM),MIN(JDIM),PSIGN(JDIM),WSIGN(JDIM),ZSIGN(JDIM) >*/
138 /*< INTEGER CH,CHS,DIFF,PROFIT,R,T >*/
139 /*< Z = 0 >*/
140 #line 65 ""
141 /* Parameter adjustments */
142 #line 65 ""
143 --zsign;
144 #line 65 ""
145 --wsign;
146 #line 65 ""
147 --psign;
148 #line 65 ""
149 --min__;
150 #line 65 ""
151 --xx;
152 #line 65 ""
153 --x;
154 #line 65 ""
155 --w;
156 #line 65 ""
157 --p;
158 #line 65 ""
159
160 #line 65 ""
161 /* Function Body */
162 #line 65 ""
163 *z__ = 0;
164 /*< IF ( JCK .EQ. 1 ) CALL CHMT1(N,P,W,C,Z,JDIM) >*/
165 #line 66 ""
166 if (*jck == 1) {
167 #line 66 ""
168 chmt1_(n, &p[1], &w[1], c__, z__, jdim);
169 #line 66 ""
170 }
171 /*< IF ( Z .LT. 0 ) RETURN >*/
172 #line 67 ""
173 if (*z__ < 0) {
174 #line 67 ""
175 return 0;
176 #line 67 ""
177 }
178 /* INITIALIZE. */
179 /*< CH = C >*/
180 #line 69 ""
181 ch = *c__;
182 /*< IP = 0 >*/
183 #line 70 ""
184 ip = 0;
185 /*< CHS = CH >*/
186 #line 71 ""
187 chs = ch;
188 /*< DO 10 LL=1,N >*/
189 #line 72 ""
190 i__1 = *n;
191 #line 72 ""
192 for (ll = 1; ll <= i__1; ++ll) {
193 /*< IF ( W(LL) .GT. CHS ) GO TO 20 >*/
194 #line 73 ""
195 if (w[ll] > chs) {
196 #line 73 ""
197 goto L20;
198 #line 73 ""
199 }
200 /*< IP = IP + P(LL) >*/
201 #line 74 ""
202 ip += p[ll];
203 /*< CHS = CHS - W(LL) >*/
204 #line 75 ""
205 chs -= w[ll];
206 /*< 10 CONTINUE >*/
207 #line 76 ""
208 /* L10: */
209 #line 76 ""
210 }
211 /*< 20 LL = LL - 1 >*/
212 #line 77 ""
213 L20:
214 #line 77 ""
215 --ll;
216 /*< IF ( CHS .EQ. 0 ) GO TO 50 >*/
217 #line 78 ""
218 if (chs == 0) {
219 #line 78 ""
220 goto L50;
221 #line 78 ""
222 }
223 /*< P(N+1) = 0 >*/
224 #line 79 ""
225 p[*n + 1] = 0;
226 /*< W(N+1) = CH + 1 >*/
227 #line 80 ""
228 w[*n + 1] = ch + 1;
229 /*< LIM = IP + CHS*P(LL+2)/W(LL+2) >*/
230 #line 81 ""
231 lim = ip + chs * p[ll + 2] / w[ll + 2];
232 /*< A = W(LL+1) - CHS >*/
233 #line 82 ""
234 a = (real) (w[ll + 1] - chs);
235 /*< B = IP + P(LL+1) >*/
236 #line 83 ""
237 b = (real) (ip + p[ll + 1]);
238 /*< LIM1 = B - A*FLOAT(P(LL))/FLOAT(W(LL)) >*/
239 #line 84 ""
240 lim1 = b - a * (real) p[ll] / (real) w[ll];
241 /*< IF ( LIM1 .GT. LIM ) LIM = LIM1 >*/
242 #line 85 ""
243 if (lim1 > lim) {
244 #line 85 ""
245 lim = lim1;
246 #line 85 ""
247 }
248 /*< MINK = CH + 1 >*/
249 #line 86 ""
250 mink = ch + 1;
251 /*< MIN(N) = MINK >*/
252 #line 87 ""
253 min__[*n] = mink;
254 /*< DO 30 J=2,N >*/
255 #line 88 ""
256 i__1 = *n;
257 #line 88 ""
258 for (j = 2; j <= i__1; ++j) {
259 /*< KK = N + 2 - J >*/
260 #line 89 ""
261 kk = *n + 2 - j;
262 /*< IF ( W(KK) .LT. MINK ) MINK = W(KK) >*/
263 #line 90 ""
264 if (w[kk] < mink) {
265 #line 90 ""
266 mink = w[kk];
267 #line 90 ""
268 }
269 /*< MIN(KK-1) = MINK >*/
270 #line 91 ""
271 min__[kk - 1] = mink;
272 /*< 30 CONTINUE >*/
273 #line 92 ""
274 /* L30: */
275 #line 92 ""
276 }
277 /*< DO 40 J=1,N >*/
278 #line 93 ""
279 i__1 = *n;
280 #line 93 ""
281 for (j = 1; j <= i__1; ++j) {
282 /*< XX(J) = 0 >*/
283 #line 94 ""
284 xx[j] = 0;
285 /*< 40 CONTINUE >*/
286 #line 95 ""
287 /* L40: */
288 #line 95 ""
289 }
290 /*< Z = 0 >*/
291 #line 96 ""
292 *z__ = 0;
293 /*< PROFIT = 0 >*/
294 #line 97 ""
295 profit = 0;
296 /*< LOLD = N >*/
297 #line 98 ""
298 lold = *n;
299 /*< II = 1 >*/
300 #line 99 ""
301 ii = 1;
302 /*< GO TO 170 >*/
303 #line 100 ""
304 goto L170;
305 /*< 50 Z = IP >*/
306 #line 101 ""
307 L50:
308 #line 101 ""
309 *z__ = ip;
310 /*< DO 60 J=1,LL >*/
311 #line 102 ""
312 i__1 = ll;
313 #line 102 ""
314 for (j = 1; j <= i__1; ++j) {
315 /*< X(J) = 1 >*/
316 #line 103 ""
317 x[j] = 1;
318 /*< 60 CONTINUE >*/
319 #line 104 ""
320 /* L60: */
321 #line 104 ""
322 }
323 /*< NN = LL + 1 >*/
324 #line 105 ""
325 nn = ll + 1;
326 /*< DO 70 J=NN,N >*/
327 #line 106 ""
328 i__1 = *n;
329 #line 106 ""
330 for (j = nn; j <= i__1; ++j) {
331 /*< X(J) = 0 >*/
332 #line 107 ""
333 x[j] = 0;
334 /*< 70 CONTINUE >*/
335 #line 108 ""
336 /* L70: */
337 #line 108 ""
338 }
339 /*< RETURN >*/
340 #line 109 ""
341 return 0;
342 /* TRY TO INSERT THE II-TH ITEM INTO THE CURRENT SOLUTION. */
343 /*< 80 IF ( W(II) .LE. CH ) GO TO 90 >*/
344 #line 111 ""
345 L80:
346 #line 111 ""
347 if (w[ii] <= ch) {
348 #line 111 ""
349 goto L90;
350 #line 111 ""
351 }
352 /*< II1 = II + 1 >*/
353 #line 112 ""
354 ii1 = ii + 1;
355 /*< IF ( Z .GE. CH*P(II1)/W(II1) + PROFIT ) GO TO 280 >*/
356 #line 113 ""
357 if (*z__ >= ch * p[ii1] / w[ii1] + profit) {
358 #line 113 ""
359 goto L280;
360 #line 113 ""
361 }
362 /*< II = II1 >*/
363 #line 114 ""
364 ii = ii1;
365 /*< GO TO 80 >*/
366 #line 115 ""
367 goto L80;
368 /* BUILD A NEW CURRENT SOLUTION. */
369 /*< 90 IP = PSIGN(II) >*/
370 #line 117 ""
371 L90:
372 #line 117 ""
373 ip = psign[ii];
374 /*< CHS = CH - WSIGN(II) >*/
375 #line 118 ""
376 chs = ch - wsign[ii];
377 /*< IN = ZSIGN(II) >*/
378 #line 119 ""
379 in = zsign[ii];
380 /*< DO 100 LL=IN,N >*/
381 #line 120 ""
382 i__1 = *n;
383 #line 120 ""
384 for (ll = in; ll <= i__1; ++ll) {
385 /*< IF ( W(LL) .GT. CHS ) GO TO 160 >*/
386 #line 121 ""
387 if (w[ll] > chs) {
388 #line 121 ""
389 goto L160;
390 #line 121 ""
391 }
392 /*< IP = IP + P(LL) >*/
393 #line 122 ""
394 ip += p[ll];
395 /*< CHS = CHS - W(LL) >*/
396 #line 123 ""
397 chs -= w[ll];
398 /*< 100 CONTINUE >*/
399 #line 124 ""
400 /* L100: */
401 #line 124 ""
402 }
403 /*< LL = N >*/
404 #line 125 ""
405 ll = *n;
406 /*< 110 IF ( Z .GE. IP + PROFIT ) GO TO 280 >*/
407 #line 126 ""
408 L110:
409 #line 126 ""
410 if (*z__ >= ip + profit) {
411 #line 126 ""
412 goto L280;
413 #line 126 ""
414 }
415 /*< Z = IP + PROFIT >*/
416 #line 127 ""
417 *z__ = ip + profit;
418 /*< NN = II - 1 >*/
419 #line 128 ""
420 nn = ii - 1;
421 /*< DO 120 J=1,NN >*/
422 #line 129 ""
423 i__1 = nn;
424 #line 129 ""
425 for (j = 1; j <= i__1; ++j) {
426 /*< X(J) = XX(J) >*/
427 #line 130 ""
428 x[j] = xx[j];
429 /*< 120 CONTINUE >*/
430 #line 131 ""
431 /* L120: */
432 #line 131 ""
433 }
434 /*< DO 130 J=II,LL >*/
435 #line 132 ""
436 i__1 = ll;
437 #line 132 ""
438 for (j = ii; j <= i__1; ++j) {
439 /*< X(J) = 1 >*/
440 #line 133 ""
441 x[j] = 1;
442 /*< 130 CONTINUE >*/
443 #line 134 ""
444 /* L130: */
445 #line 134 ""
446 }
447 /*< IF ( LL .EQ. N ) GO TO 150 >*/
448 #line 135 ""
449 if (ll == *n) {
450 #line 135 ""
451 goto L150;
452 #line 135 ""
453 }
454 /*< NN = LL + 1 >*/
455 #line 136 ""
456 nn = ll + 1;
457 /*< DO 140 J=NN,N >*/
458 #line 137 ""
459 i__1 = *n;
460 #line 137 ""
461 for (j = nn; j <= i__1; ++j) {
462 /*< X(J) = 0 >*/
463 #line 138 ""
464 x[j] = 0;
465 /*< 140 CONTINUE >*/
466 #line 139 ""
467 /* L140: */
468 #line 139 ""
469 }
470 /*< 150 IF ( Z .NE. LIM ) GO TO 280 >*/
471 #line 140 ""
472 L150:
473 #line 140 ""
474 if (*z__ != lim) {
475 #line 140 ""
476 goto L280;
477 #line 140 ""
478 }
479 /*< RETURN >*/
480 #line 141 ""
481 return 0;
482 /*< 160 IU = CHS*P(LL)/W(LL) >*/
483 #line 142 ""
484 L160:
485 #line 142 ""
486 iu = chs * p[ll] / w[ll];
487 /*< LL = LL - 1 >*/
488 #line 143 ""
489 --ll;
490 /*< IF ( IU .EQ. 0 ) GO TO 110 >*/
491 #line 144 ""
492 if (iu == 0) {
493 #line 144 ""
494 goto L110;
495 #line 144 ""
496 }
497 /*< IF ( Z .GE. PROFIT + IP + IU ) GO TO 280 >*/
498 #line 145 ""
499 if (*z__ >= profit + ip + iu) {
500 #line 145 ""
501 goto L280;
502 #line 145 ""
503 }
504 /* SAVE THE CURRENT SOLUTION. */
505 /*< 170 WSIGN(II) = CH - CHS >*/
506 #line 147 ""
507 L170:
508 #line 147 ""
509 wsign[ii] = ch - chs;
510 /*< PSIGN(II) = IP >*/
511 #line 148 ""
512 psign[ii] = ip;
513 /*< ZSIGN(II) = LL + 1 >*/
514 #line 149 ""
515 zsign[ii] = ll + 1;
516 /*< XX(II) = 1 >*/
517 #line 150 ""
518 xx[ii] = 1;
519 /*< NN = LL - 1 >*/
520 #line 151 ""
521 nn = ll - 1;
522 /*< IF ( NN .LT. II) GO TO 190 >*/
523 #line 152 ""
524 if (nn < ii) {
525 #line 152 ""
526 goto L190;
527 #line 152 ""
528 }
529 /*< DO 180 J=II,NN >*/
530 #line 153 ""
531 i__1 = nn;
532 #line 153 ""
533 for (j = ii; j <= i__1; ++j) {
534 /*< WSIGN(J+1) = WSIGN(J) - W(J) >*/
535 #line 154 ""
536 wsign[j + 1] = wsign[j] - w[j];
537 /*< PSIGN(J+1) = PSIGN(J) - P(J) >*/
538 #line 155 ""
539 psign[j + 1] = psign[j] - p[j];
540 /*< ZSIGN(J+1) = LL + 1 >*/
541 #line 156 ""
542 zsign[j + 1] = ll + 1;
543 /*< XX(J+1) = 1 >*/
544 #line 157 ""
545 xx[j + 1] = 1;
546 /*< 180 CONTINUE >*/
547 #line 158 ""
548 /* L180: */
549 #line 158 ""
550 }
551 /*< 190 J1 = LL + 1 >*/
552 #line 159 ""
553 L190:
554 #line 159 ""
555 j1 = ll + 1;
556 /*< DO 200 J=J1,LOLD >*/
557 #line 160 ""
558 i__1 = lold;
559 #line 160 ""
560 for (j = j1; j <= i__1; ++j) {
561 /*< WSIGN(J) = 0 >*/
562 #line 161 ""
563 wsign[j] = 0;
564 /*< PSIGN(J) = 0 >*/
565 #line 162 ""
566 psign[j] = 0;
567 /*< ZSIGN(J) = J >*/
568 #line 163 ""
569 zsign[j] = j;
570 /*< 200 CONTINUE >*/
571 #line 164 ""
572 /* L200: */
573 #line 164 ""
574 }
575 /*< LOLD = LL >*/
576 #line 165 ""
577 lold = ll;
578 /*< CH = CHS >*/
579 #line 166 ""
580 ch = chs;
581 /*< PROFIT = PROFIT + IP >*/
582 #line 167 ""
583 profit += ip;
584 /*< IF ( LL - (N - 2) ) 240, 220, 210 >*/
585 #line 168 ""
586 if ((i__1 = ll - (*n - 2)) < 0) {
587 #line 168 ""
588 goto L240;
589 #line 168 ""
590 } else if (i__1 == 0) {
591 #line 168 ""
592 goto L220;
593 #line 168 ""
594 } else {
595 #line 168 ""
596 goto L210;
597 #line 168 ""
598 }
599 /*< 210 II = N >*/
600 #line 169 ""
601 L210:
602 #line 169 ""
603 ii = *n;
604 /*< GO TO 250 >*/
605 #line 170 ""
606 goto L250;
607 /*< 220 IF ( CH .LT. W(N) ) GO TO 230 >*/
608 #line 171 ""
609 L220:
610 #line 171 ""
611 if (ch < w[*n]) {
612 #line 171 ""
613 goto L230;
614 #line 171 ""
615 }
616 /*< CH = CH - W(N) >*/
617 #line 172 ""
618 ch -= w[*n];
619 /*< PROFIT = PROFIT + P(N) >*/
620 #line 173 ""
621 profit += p[*n];
622 /*< XX(N) = 1 >*/
623 #line 174 ""
624 xx[*n] = 1;
625 /*< 230 II = N - 1 >*/
626 #line 175 ""
627 L230:
628 #line 175 ""
629 ii = *n - 1;
630 /*< GO TO 250 >*/
631 #line 176 ""
632 goto L250;
633 /*< 240 II = LL + 2 >*/
634 #line 177 ""
635 L240:
636 #line 177 ""
637 ii = ll + 2;
638 /*< IF ( CH .GE. MIN(II-1) ) GO TO 80 >*/
639 #line 178 ""
640 if (ch >= min__[ii - 1]) {
641 #line 178 ""
642 goto L80;
643 #line 178 ""
644 }
645 /* SAVE THE CURRENT OPTIMAL SOLUTION. */
646 /*< 250 IF ( Z .GE. PROFIT ) GO TO 270 >*/
647 #line 180 ""
648 L250:
649 #line 180 ""
650 if (*z__ >= profit) {
651 #line 180 ""
652 goto L270;
653 #line 180 ""
654 }
655 /*< Z = PROFIT >*/
656 #line 181 ""
657 *z__ = profit;
658 /*< DO 260 J=1,N >*/
659 #line 182 ""
660 i__1 = *n;
661 #line 182 ""
662 for (j = 1; j <= i__1; ++j) {
663 /*< X(J) = XX(J) >*/
664 #line 183 ""
665 x[j] = xx[j];
666 /*< 260 CONTINUE >*/
667 #line 184 ""
668 /* L260: */
669 #line 184 ""
670 }
671 /*< IF ( Z .EQ. LIM ) RETURN >*/
672 #line 185 ""
673 if (*z__ == lim) {
674 #line 185 ""
675 return 0;
676 #line 185 ""
677 }
678 /*< 270 IF ( XX(N) .EQ. 0 ) GO TO 280 >*/
679 #line 186 ""
680 L270:
681 #line 186 ""
682 if (xx[*n] == 0) {
683 #line 186 ""
684 goto L280;
685 #line 186 ""
686 }
687 /*< XX(N) = 0 >*/
688 #line 187 ""
689 xx[*n] = 0;
690 /*< CH = CH + W(N) >*/
691 #line 188 ""
692 ch += w[*n];
693 /*< PROFIT = PROFIT - P(N) >*/
694 #line 189 ""
695 profit -= p[*n];
696 /* BACKTRACK. */
697 /*< 280 NN = II - 1 >*/
698 #line 191 ""
699 L280:
700 #line 191 ""
701 nn = ii - 1;
702 /*< IF ( NN .EQ. 0 ) RETURN >*/
703 #line 192 ""
704 if (nn == 0) {
705 #line 192 ""
706 return 0;
707 #line 192 ""
708 }
709 /*< DO 290 J=1,NN >*/
710 #line 193 ""
711 i__1 = nn;
712 #line 193 ""
713 for (j = 1; j <= i__1; ++j) {
714 /*< KK = II - J >*/
715 #line 194 ""
716 kk = ii - j;
717 /*< IF ( XX(KK) .EQ. 1 ) GO TO 300 >*/
718 #line 195 ""
719 if (xx[kk] == 1) {
720 #line 195 ""
721 goto L300;
722 #line 195 ""
723 }
724 /*< 290 CONTINUE >*/
725 #line 196 ""
726 /* L290: */
727 #line 196 ""
728 }
729 /*< RETURN >*/
730 #line 197 ""
731 return 0;
732 /*< 300 R = CH >*/
733 #line 198 ""
734 L300:
735 #line 198 ""
736 r__ = ch;
737 /*< CH = CH + W(KK) >*/
738 #line 199 ""
739 ch += w[kk];
740 /*< PROFIT = PROFIT - P(KK) >*/
741 #line 200 ""
742 profit -= p[kk];
743 /*< XX(KK) = 0 >*/
744 #line 201 ""
745 xx[kk] = 0;
746 /*< IF ( R .LT. MIN(KK) ) GO TO 310 >*/
747 #line 202 ""
748 if (r__ < min__[kk]) {
749 #line 202 ""
750 goto L310;
751 #line 202 ""
752 }
753 /*< II = KK + 1 >*/
754 #line 203 ""
755 ii = kk + 1;
756 /*< GO TO 80 >*/
757 #line 204 ""
758 goto L80;
759 /*< 310 NN = KK + 1 >*/
760 #line 205 ""
761 L310:
762 #line 205 ""
763 nn = kk + 1;
764 /*< II = KK >*/
765 #line 206 ""
766 ii = kk;
767 /* TRY TO SUBSTITUTE THE NN-TH ITEM FOR THE KK-TH. */
768 /*< 320 IF ( Z .GE. PROFIT + CH*P(NN)/W(NN) ) GO TO 280 >*/
769 #line 208 ""
770 L320:
771 #line 208 ""
772 if (*z__ >= profit + ch * p[nn] / w[nn]) {
773 #line 208 ""
774 goto L280;
775 #line 208 ""
776 }
777 /*< DIFF = W(NN) - W(KK) >*/
778 #line 209 ""
779 diff = w[nn] - w[kk];
780 /*< IF ( DIFF ) 370, 330, 340 >*/
781 #line 210 ""
782 if (diff < 0) {
783 #line 210 ""
784 goto L370;
785 #line 210 ""
786 } else if (diff == 0) {
787 #line 210 ""
788 goto L330;
789 #line 210 ""
790 } else {
791 #line 210 ""
792 goto L340;
793 #line 210 ""
794 }
795 /*< 330 NN = NN + 1 >*/
796 #line 211 ""
797 L330:
798 #line 211 ""
799 ++nn;
800 /*< GO TO 320 >*/
801 #line 212 ""
802 goto L320;
803 /*< 340 IF ( DIFF .GT. R ) GO TO 330 >*/
804 #line 213 ""
805 L340:
806 #line 213 ""
807 if (diff > r__) {
808 #line 213 ""
809 goto L330;
810 #line 213 ""
811 }
812 /*< IF ( Z .GE. PROFIT + P(NN) ) GO TO 330 >*/
813 #line 214 ""
814 if (*z__ >= profit + p[nn]) {
815 #line 214 ""
816 goto L330;
817 #line 214 ""
818 }
819 /*< Z = PROFIT + P(NN) >*/
820 #line 215 ""
821 *z__ = profit + p[nn];
822 /*< DO 350 J=1,KK >*/
823 #line 216 ""
824 i__1 = kk;
825 #line 216 ""
826 for (j = 1; j <= i__1; ++j) {
827 /*< X(J) = XX(J) >*/
828 #line 217 ""
829 x[j] = xx[j];
830 /*< 350 CONTINUE >*/
831 #line 218 ""
832 /* L350: */
833 #line 218 ""
834 }
835 /*< JJ = KK + 1 >*/
836 #line 219 ""
837 jj = kk + 1;
838 /*< DO 360 J=JJ,N >*/
839 #line 220 ""
840 i__1 = *n;
841 #line 220 ""
842 for (j = jj; j <= i__1; ++j) {
843 /*< X(J) = 0 >*/
844 #line 221 ""
845 x[j] = 0;
846 /*< 360 CONTINUE >*/
847 #line 222 ""
848 /* L360: */
849 #line 222 ""
850 }
851 /*< X(NN) = 1 >*/
852 #line 223 ""
853 x[nn] = 1;
854 /*< IF ( Z .EQ. LIM ) RETURN >*/
855 #line 224 ""
856 if (*z__ == lim) {
857 #line 224 ""
858 return 0;
859 #line 224 ""
860 }
861 /*< R = R - DIFF >*/
862 #line 225 ""
863 r__ -= diff;
864 /*< KK = NN >*/
865 #line 226 ""
866 kk = nn;
867 /*< NN = NN + 1 >*/
868 #line 227 ""
869 ++nn;
870 /*< GO TO 320 >*/
871 #line 228 ""
872 goto L320;
873 /*< 370 T = R - DIFF >*/
874 #line 229 ""
875 L370:
876 #line 229 ""
877 t = r__ - diff;
878 /*< IF ( T .LT. MIN(NN) ) GO TO 330 >*/
879 #line 230 ""
880 if (t < min__[nn]) {
881 #line 230 ""
882 goto L330;
883 #line 230 ""
884 }
885 /*< IF ( Z .GE. PROFIT + P(NN) + T*P(NN+1)/W(NN+1)) GO TO 280 >*/
886 #line 231 ""
887 if (*z__ >= profit + p[nn] + t * p[nn + 1] / w[nn + 1]) {
888 #line 231 ""
889 goto L280;
890 #line 231 ""
891 }
892 /*< CH = CH - W(NN) >*/
893 #line 232 ""
894 ch -= w[nn];
895 /*< PROFIT = PROFIT + P(NN) >*/
896 #line 233 ""
897 profit += p[nn];
898 /*< XX(NN) = 1 >*/
899 #line 234 ""
900 xx[nn] = 1;
901 /*< II = NN + 1 >*/
902 #line 235 ""
903 ii = nn + 1;
904 /*< WSIGN(NN) = W(NN) >*/
905 #line 236 ""
906 wsign[nn] = w[nn];
907 /*< PSIGN(NN) = P(NN) >*/
908 #line 237 ""
909 psign[nn] = p[nn];
910 /*< ZSIGN(NN) = II >*/
911 #line 238 ""
912 zsign[nn] = ii;
913 /*< N1 = NN + 1 >*/
914 #line 239 ""
915 n1 = nn + 1;
916 /*< DO 380 J=N1,LOLD >*/
917 #line 240 ""
918 i__1 = lold;
919 #line 240 ""
920 for (j = n1; j <= i__1; ++j) {
921 /*< WSIGN(J) = 0 >*/
922 #line 241 ""
923 wsign[j] = 0;
924 /*< PSIGN(J) = 0 >*/
925 #line 242 ""
926 psign[j] = 0;
927 /*< ZSIGN(J) = J >*/
928 #line 243 ""
929 zsign[j] = j;
930 /*< 380 CONTINUE >*/
931 #line 244 ""
932 /* L380: */
933 #line 244 ""
934 }
935 /*< LOLD = NN >*/
936 #line 245 ""
937 lold = nn;
938 /*< GO TO 80 >*/
939 #line 246 ""
940 goto L80;
941 /*< END >*/
942 } /* mt1_ */
943
944 /*< SUBROUTINE CHMT1(N,P,W,C,Z,JDIM) >*/
945 #if 1 /* by mao */
946 static
947 #endif
chmt1_(integer * n,integer * p,integer * w,integer * c__,integer * z__,integer * jdim)948 /* Subroutine */ int chmt1_(integer *n, integer *p, integer *w, integer *c__,
949 integer *z__, integer *jdim)
950 {
951 /* System generated locals */
952 integer i__1;
953
954 /* Local variables */
955 static integer j;
956 static real r__, rr;
957 static integer jsw;
958
959
960 /* CHECK THE INPUT DATA. */
961
962 /*< INTEGER P(JDIM),W(JDIM),C,Z >*/
963 /*< IF ( N .GE. 2 .AND. N .LE. JDIM - 1 ) GO TO 10 >*/
964 #line 253 ""
965 /* Parameter adjustments */
966 #line 253 ""
967 --w;
968 #line 253 ""
969 --p;
970 #line 253 ""
971
972 #line 253 ""
973 /* Function Body */
974 #line 253 ""
975 if (*n >= 2 && *n <= *jdim - 1) {
976 #line 253 ""
977 goto L10;
978 #line 253 ""
979 }
980 /*< Z = - 1 >*/
981 #line 254 ""
982 *z__ = -1;
983 /*< RETURN >*/
984 #line 255 ""
985 return 0;
986 /*< 10 IF ( C .GT. 0 ) GO TO 30 >*/
987 #line 256 ""
988 L10:
989 #line 256 ""
990 if (*c__ > 0) {
991 #line 256 ""
992 goto L30;
993 #line 256 ""
994 }
995 /*< 20 Z = - 2 >*/
996 #line 257 ""
997 L20:
998 #line 257 ""
999 *z__ = -2;
1000 /*< RETURN >*/
1001 #line 258 ""
1002 return 0;
1003 /*< 30 JSW = 0 >*/
1004 #line 259 ""
1005 L30:
1006 #line 259 ""
1007 jsw = 0;
1008 /*< RR = FLOAT(P(1))/FLOAT(W(1)) >*/
1009 #line 260 ""
1010 rr = (real) p[1] / (real) w[1];
1011 /*< DO 50 J=1,N >*/
1012 #line 261 ""
1013 i__1 = *n;
1014 #line 261 ""
1015 for (j = 1; j <= i__1; ++j) {
1016 /*< R = RR >*/
1017 #line 262 ""
1018 r__ = rr;
1019 /*< IF ( P(J) .LE. 0 ) GO TO 20 >*/
1020 #line 263 ""
1021 if (p[j] <= 0) {
1022 #line 263 ""
1023 goto L20;
1024 #line 263 ""
1025 }
1026 /*< IF ( W(J) .LE. 0 ) GO TO 20 >*/
1027 #line 264 ""
1028 if (w[j] <= 0) {
1029 #line 264 ""
1030 goto L20;
1031 #line 264 ""
1032 }
1033 /*< JSW = JSW + W(J) >*/
1034 #line 265 ""
1035 jsw += w[j];
1036 /*< IF ( W(J) .LE. C ) GO TO 40 >*/
1037 #line 266 ""
1038 if (w[j] <= *c__) {
1039 #line 266 ""
1040 goto L40;
1041 #line 266 ""
1042 }
1043 /*< Z = - 3 >*/
1044 #line 267 ""
1045 *z__ = -3;
1046 /*< RETURN >*/
1047 #line 268 ""
1048 return 0;
1049 /*< 40 RR = FLOAT(P(J))/FLOAT(W(J)) >*/
1050 #line 269 ""
1051 L40:
1052 #line 269 ""
1053 rr = (real) p[j] / (real) w[j];
1054 /*< IF ( RR .LE. R ) GO TO 50 >*/
1055 #line 270 ""
1056 if (rr <= r__) {
1057 #line 270 ""
1058 goto L50;
1059 #line 270 ""
1060 }
1061 /*< Z = - 5 >*/
1062 #line 271 ""
1063 *z__ = -5;
1064 /*< RETURN >*/
1065 #line 272 ""
1066 return 0;
1067 /*< 50 CONTINUE >*/
1068 #line 273 ""
1069 L50:
1070 #line 273 ""
1071 ;
1072 #line 273 ""
1073 }
1074 /*< IF ( JSW .GT. C ) RETURN >*/
1075 #line 274 ""
1076 if (jsw > *c__) {
1077 #line 274 ""
1078 return 0;
1079 #line 274 ""
1080 }
1081 /*< Z = - 4 >*/
1082 #line 275 ""
1083 *z__ = -4;
1084 /*< RETURN >*/
1085 #line 276 ""
1086 return 0;
1087 /*< END >*/
1088 } /* chmt1_ */
1089
1090 #if 1 /* by mao */
mt1(int n,int p[],int w[],int c,int x[],int jck,int xx[],int min[],int psign[],int wsign[],int zsign[])1091 int mt1(int n, int p[], int w[], int c, int x[], int jck, int xx[],
1092 int min[], int psign[], int wsign[], int zsign[])
1093 { /* solve 0-1 knapsack problem */
1094 int z, jdim = n+1, j, s1, s2;
1095 mt1_(&n, &p[1], &w[1], &c, &z, &x[1], &jdim, &jck, &xx[1],
1096 &min[1], &psign[1], &wsign[1], &zsign[1]);
1097 /* check solution found */
1098 s1 = s2 = 0;
1099 for (j = 1; j <= n; j++)
1100 { xassert(x[j] == 0 || x[j] == 1);
1101 if (x[j])
1102 s1 += p[j], s2 += w[j];
1103 }
1104 xassert(s1 == z);
1105 xassert(s2 <= c);
1106 return z;
1107 }
1108 #endif
1109
1110 /* eof */
1111