[Bài tập] Các bài tập quy hoạch động cơ bản

Nhà trường có một phòng hội trường. Có những yêu cầu muốn sử dụng phòng hội trường này, mỗi yêu cầu cho biết thời điểm bắt đầu và thời điểm kết thúc. Nhà trường có thể chấp nhận hoặc từ chối đối với một yêu cầu.

Yêu cầu: hãy giúp nhà trường chọn các yêu cầu sử dụng hội trường sao cho tổng thời gian hội trường được sử dụng là lớn nhất.

INPUT:
Dòng đầu tiên chứa một số nguyên dương n (n ≤ 10000), số yêu cầu.

Mỗi dòng trong số n dòng tiếp theo chứa 2 số nguyên dương p và k (0 ≤ p < k ≤ 30000), mô tả một yêu cầu bắt đầu tại thời điểm p và kết thúc tại thời điểm k.

OUTPUT:
Gồm một dòng duy nhất là tổng thời gian lớn nhất mà hội trường được sử dụng

Ví dụ:

Code:


Input:
12
1 2
3 5
0 4
6 8
7 13
4 6
9 10
9 12
11 14
15 19
14 16
18 20
Output: 16

Một cơ sở sửa chữa ô tô có nhận n chiếc xe để sửa. Do các nhân viên làm việc quá lười nhác nên đã đến hạn trả cho khách hàng mà vẫn chưa tiến hành sửa được chiếc xe nào. Theo hợp đồng đã ký kết từ trước, nếu bàn giao xe thứ i quá hạn ngày nào thì sẽ phải trả thêm một khoản tiền phạt là A[i].
Ông chủ cơ sở sửa chữa quyết định sa thải toàn bộ công nhân và thuê nhân công mới. Với lực lượng mới này, ông ta dự định rằng để sửa chiếc xe thứ i sẽ cần B[i] ngày. Vấn đề đặt ra đối với ông là phải lập lịch sửa tuần tự các chiếc xe sao cho tổng số tiền bị phạt là ít nhất.

Yêu cầu: Hãy lập lịch sửa xe giúp cho ông chủ cơ sở sửa chữa ô tô.

INPUT
• Dòng 1: Chứa số n (n ≤ 10000)
• Dòng 2: Chứa n số nguyên dương A[1], A[2], ..., A[n] (1 ≤ A[i] ≤ 10000)
• Dòng 3: Chứa n số nguyên dương B[1], B[2], ..., B[n] (1 ≤ B[i] ≤ 100)

OUTPUT
• Dòng 1: Ghi số tiền bị phạt tối thiểu
• Dòng 2: Ghi số hiệu các xe sẽ tiến hành sửa chữa, theo thứ tự từ xe được sửa đầu tiên đến xe sửa sau cùng

Ví dụ:

Code:


Input:
4
1 3 4 2
3 2 3 1

Output:
44
4 2 3 1

Giải thích:

Code:


Xong công việc 4 vào cuối ngày 1 => phải trả 2 * 1 = 2 .
Xong công việc 2 vào cuối ngày 3 => phải trả 3 * 3 = 9.
Xong công việc 3 vào cuối ngày 6 => phải trả 6 * 4 = 24 .
Xong công việc 1 vào cuối ngày 9 => phải trả 1 * 9 = 9 .
Vậy tổng cộng phải trả 44 .

Nông dân John đang đưa các con bò của anh ta đi xem phim! Xe tải của anh ta thì có sức chứa có hạn thôi, là C (100 <= C <= 5000) kg, anh ta muốn đưa 1 số con bò đi xem phim sao cho tổng khối lượng của đống bò này là lớn nhất, đồng thời xe tải của anh ta vẫn chịu được.

Cho N (1 <= N <= 16) con bò và khối lượng W_i của từng con, hãy cho biết khối lượng bò lớn nhất mà John có thể đưa đi xem phim là bao nhiêu.

INPUT
•Dòng 1: 2 số nguyên cách nhau bởi dấu cách: C và N
•Dòng 2..N+1: Dòng i+1 chứa 1 số nguyên: W_i

OUTPUT
•Ghi ra một số nguyên là tổng khối lượng bò lớn nhất mà John có thể mang đi xem phim.

Ví dụ:

Code:


Input
259 5
81
58
42
33
61

Output
242

Giải thích:

Code:


81+58+42+61 = 242; đây là tổng khối lượng bò lớn nhất có thể được.

Cho một dãy số nguyên gồm N phần tử A[1], A[2], ... A[N].
Biết rằng dãy con tăng đơn điệu là 1 dãy A[i1],... A[ik] thỏa mãn
i1 < i2 < ... < ik và A[i1] < A[i2] < .. < A[ik]. Hãy cho biết dãy con tăng đơn điệu dài nhất của dãy này có bao nhiêu phần tử?

INPUT
•Dòng 1 gồm 1 số nguyên là số N (1 ≤ N ≤ 1000).
•Dòng thứ 2 ghi N số nguyên A[1], A[2], .. A[N] (1 ≤ A[i] ≤ 10000).

OUTPUT
•Ghi ra độ dài của dãy con tăng đơn điệu dài nhất.

Ví dụ:

Code:


Input:
6
1 2 5 4 6 2

Output:
4

sao không thấy code vậy bạn, mà chỉ có bộ test thui

chuot_177 wrote:sao không thấy code vậy bạn, mà chỉ có bộ test thui

Mấy bài này cơ bản mà bạn - Bạn có thể tự code được mà còn cái click vào để xem code là chế độ ẩn với khách

có thấy code để tham khảo đâu bạn

nnsanh78 wrote:có thấy code để tham khảo đâu bạn

À mấy bài này cơ bản nên mình không post lên [You must be registered and logged in to see this image.]

Bác gì ời bài này giải bằng phương pháp quy hoạch động được không bác. Mong bác chỉ giúp

[You must be registered and logged in to see this link.]

post cả code lên đi ad ơi

ad cho em post code bài Đi xem phim nha
thuật toán: gọi f[i] là khả năng phân tích i thành tổng một dãy con của w. f[i] = true: có ngược lại không. sau đó duyệt từ c đến 0 (để chọn được kq lớn nhất có thể) nếu f[i] = true thì báo kết quả và thoát.

Code:


var f:array [0..5000] of boolean;
    w:array [1..16] of integer;
    c,n,i,j:integer;
begin                 
        readln(c,n);
        for i:=1 to n do readln(w[i]);

        f[0]:=true;
        for i:=1 to n do
        for j:=c downto w[i] do
          f[j]:=f[j] or f[j-w[i]];

        for i:=c downto 0 do
        if f[i] then
          begin
                writeln(i); exit;
          end;
end.


pha96 wrote:ad cho em post code bài Đi xem phim nha
thuật toán: gọi f[i] là khả năng phân tích i thành tổng một dãy con của w. f[i] = true: có ngược lại không. sau đó duyệt từ c đến 0 (để chọn được kq lớn nhất có thể) nếu f[i] = true thì báo kết quả và thoát.

Code:


var f:array [0..5000] of boolean;
    w:array [1..16] of integer;
    c,n,i,j:integer;
begin                 
        readln(c,n);
        for i:=1 to n do readln(w[i]);

        f[0]:=true;
        for i:=1 to n do
        for j:=c downto w[i] do
          f[j]:=f[j] or f[j-w[i]];

        for i:=c downto 0 do
        if f[i] then
          begin
                writeln(i); exit;
          end;
end.


Một cách khác là áp dụng công thức QHĐ giống bài Knapsack (Cái túi)
Giá trị của mỗi con bò sẽ chính là khối lượng của nó, ta sẽ tìm cách chọn những con bò sao cho tổng giá trị là lớn nhất và không vượt quá W.

Code:

 
for i:=1 to n do
    for j:=1 to w do
        if a[i]<=j then F[i,j]:=max(F[i-1,j],F[i-1,j-a[i]]+a[i])
        else f[i,j]:=f[i-1,j];


Khi đó kết quả của bài toán sẽ là F[n,w]

code bài 4 đây
gọi f[i] là độ dài dãy con dài nhất kết thúc tại i, ta sẽ chọn f[j] sao cho f[j] là lớn nhất và a[j] phải nhỏ hơn a[i] để đảm bảo điều kiện dài nhất và dãy tăng (j=1..i-1). kết quả bài toán là max(f[1], f[2],...., f[n]).

Code:


var a,f:array [1..1000] of longint;
    n,i,j,res:integer;
begin
    readln(n);
    read(a[1]);
    f[1]:=1; res:=1;
    for i:=2 to n do
    begin
        read(a[i]);
        f[i]:=1;
        for j:=1 to i-1 do
        if (a[i] > a[j]) and (f[j] + 1 > f[i]) then f[i]:=f[j] + 1;
        if res < f[i] then res:=f[i];
    end;
    writeln(res);
    readln
end.


add ơi giúp mình giải các bài trên với code C với