HỌC TIN CÙNG THỦ KHOA

Mời các bạn Download code tại: Click here

Program XepBaLo0_1;
uses crt;
const MAXN = 20;
var n: integer;
    M: real;
    W: array [1..MAXN] of real;
    V: array [1..MAXN] of real;
    a: array [1..MAXN] of boolean;
    x: array [1..MAXN] of boolean;
    weight, value, vmax: real;

procedure Nhap;
var i: integer;
begin
        write('Nhap N = '); readln(n);
        write('Nhap suc chua cua ba lo: '); readln(M);
        for i:= 1 to n do
        begin
                writeln('Nhap thong tin cua do vat thu ', i, ': ');
                write('   - Trong luong: '); readln(W[i]);
                write('   - Gia tri: '); readln(V[i]);
        end;
end;

procedure Init;
begin
        vmax:= -1;
        weight:= 0;
        value:= 0;
end;

procedure Update;
var i: integer;
begin
        if weight <= M then
        begin
                if value > vmax then
                begin
                        vmax:= value;
                        for i:= 1 to n do
                                x[i]:= a[i];
                end;
        end;

end;

procedure Try2(i: integer);
var j: boolean;
begin
        for j:= false to true do
        begin
                a[i]:= j;
                if j = true then
                begin
                        weight:= weight + W[i];
                        value:= value + V[i];
                end;
                if weight <= M then // Dieu kien nhanh can
                begin
                        if i = n then Update
                                else Try2(i+1);
                end;
                if j = true then
                begin
                        weight:= weight - W[i];
                        value:= value - V[i];
                end;
        end;
end;

procedure InKQ;
var i: integer;
begin
        writeln('Tong gia tri lon nhat: ', vmax:0:2);
        writeln('Chon cac do vat sau: ');
        for i:= 1 to n do
                if x[i] = true then
                        write(i, '   ');
end;

BEGIN
        CLRSCR;
        Nhap;
        Init;
        Try2(1);
        InKQ;
        READLN;

END.