Informatika gyűjtemény

Egy szinttel feljebb fg_teher.dpr

2004050607080910

<<  5. óra  >>

<<  Teher-fuvar  >>

NézetNyomtat

fg_teher.dpr (Vissza)
Az alábbi letöltési lehetőségek közül választhatsz: (segítség)
Karakterkódolás:
Sortörés:
Típus: text/plain
Tartalmaz szöveget
Karakterkódolás: us-ascii
Méret: 2 KB
{$A+,B-,C+,D+,E-,F-,G+,H+,I+,J-,K-,L+,M-,N+,O+,P+,Q+,R+,S-,T-,U+,V+,W+,X+,Y+,Z1}
{$MINSTACKSIZE $00004000}
{$MAXSTACKSIZE $00100000}
{$IMAGEBASE $00400000}
{$APPTYPE CONSOLE}

PROGRAM teher;
USES SysUtils;

CONST
    maxn = 50;
    maxk = 200;

    ch = '1';
    inputFile = 'teher'+ch+'.be';
    outputFile = 'teher'+ch+'.kix';

VAR
    N, K: BYTE;
    s: ARRAY [1..maxn] OF INTEGER;
    e: ARRAY [1..maxn] OF INTEGER;


    cache: ARRAY [1..maxn+1, 0..maxk] OF INTEGER;
    choice: ARRAY [1..maxn, 0..maxk] OF BOOLEAN;

PROCEDURE Load;
VAR
    T: Text;
    i: INTEGER;
BEGIN
    Assign(T, inputFile);
    Reset(T);
    ReadLn(T, N, K);
    FOR i:= 1 TO N DO
    BEGIN
        ReadLn(T, e[i], s[i]);
    END;
    Close(T);
END; {Load}

FUNCTION Legjobb(hely, marad: BYTE): INTEGER;
VAR
    ertek, ertek0: INTEGER;
BEGIN
    IF cache[hely, marad] = -1 THEN
    BEGIN
        IF (marad = 0) OR (hely > N) THEN cache[hely, marad]:= 0
        ELSE
        BEGIN
            ertek:= Legjobb(hely+1, marad);
            choice[hely, marad]:= FALSE;
            IF s[hely] <= marad THEN
            BEGIN
                ertek0:= e[hely] + Legjobb(hely+1, marad-s[hely]);
                IF ertek0 > ertek THEN
                BEGIN
                    ertek:= ertek0;
                    choice[hely, marad]:= TRUE;
                END;
            END;
            cache[hely, marad]:= ertek;
        END;
    END;

    Legjobb:= cache[hely, marad];
END; {Legjobb}

PROCEDURE Process;
VAR
    i, j: INTEGER;
    marad: BYTE;

    T: Text;
BEGIN
    FOR j:= 0 TO maxk DO
    BEGIN
        cache[maxn+1, j]:= -1;
        FOR i:= 1 TO maxn DO
        BEGIN
            cache[i, j]:= -1;
            choice[i, j]:= FALSE;
        END;
    END;

    Assign(T, outputFile);
    Rewrite(T);

    WriteLn( T, Legjobb(1, K) );

    marad:= K;
    FOR i:= 1 TO N DO
    BEGIN
        IF choice[i, marad] THEN
        BEGIN
            WriteLn(T, i);
            marad:= marad - s[i];
        END;
    END;

    Close(T);
END; {Process}

BEGIN
    Load;
    Process;
END.
(Vissza)