Tin học Việt

A place for learning and sharing knowledge


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

    Share

    Admin
    Admin
    Admin

    Posts : 48
    Golds : 2147483647
    Liked : 16
    Ngày tham gia : 2011-08-25
    Tuổi : 20
    Đến từ : Ho Chi Minh City

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

    Post by Admin on Sun Feb 05, 2012 6:29 pm

    - HỘI TRƯỜNG -
    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

    - Lập lịch sữa chữa xe -
    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 .

    - Đi xem phim -
    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.

    - Dãy con tăng dài nhất -
    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

    chuot_177

    Posts : 1
    Golds : 1
    Liked : 0
    Ngày tham gia : 2012-02-28

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

    Post by chuot_177 on Tue Feb 28, 2012 8:17 am

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

    Admin
    Admin
    Admin

    Posts : 48
    Golds : 2147483647
    Liked : 16
    Ngày tham gia : 2011-08-25
    Tuổi : 20
    Đến từ : Ho Chi Minh City

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

    Post by Admin on Tue Feb 28, 2012 3:35 pm

    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

    nnsanh78

    Posts : 1
    Golds : 1
    Liked : 0
    Ngày tham gia : 2012-06-16

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

    Post by nnsanh78 on Sun Jun 17, 2012 8:18 am

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

    Admin
    Admin
    Admin

    Posts : 48
    Golds : 2147483647
    Liked : 16
    Ngày tham gia : 2011-08-25
    Tuổi : 20
    Đến từ : Ho Chi Minh City

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

    Post by Admin on Mon Jun 18, 2012 3:41 pm

    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.]

    Chuheokhaukhinh

    Posts : 2
    Golds : 4
    Liked : 0
    Ngày tham gia : 2012-10-26

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

    Post by Chuheokhaukhinh on Fri Oct 26, 2012 6:16 pm

    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.]

    ngocanh

    Posts : 1
    Golds : 1
    Liked : 0
    Ngày tham gia : 2013-04-11

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

    Post by ngocanh on Thu Apr 11, 2013 8:35 pm

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

    pha96
    Mod
    Mod

    Posts : 5
    Golds : 11
    Liked : 4
    Ngày tham gia : 2013-01-23
    Tuổi : 20

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

    Post by pha96 on Sat Apr 13, 2013 5:17 pm

    ad cho em post code bài Đi xem phim nha :d
    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.

    Admin
    Admin
    Admin

    Posts : 48
    Golds : 2147483647
    Liked : 16
    Ngày tham gia : 2011-08-25
    Tuổi : 20
    Đến từ : Ho Chi Minh City

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

    Post by Admin on Sat Apr 13, 2013 7:26 pm

    pha96 wrote:ad cho em post code bài Đi xem phim nha :d
    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]




    Last edited by Admin on Sun Apr 14, 2013 11:29 am; edited 1 time in total

    pha96
    Mod
    Mod

    Posts : 5
    Golds : 11
    Liked : 4
    Ngày tham gia : 2013-01-23
    Tuổi : 20

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

    Post by pha96 on Sat Apr 13, 2013 8:46 pm

    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.

    popperdk

    Posts : 1
    Golds : 1
    Liked : 0
    Ngày tham gia : 2015-04-28

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

    Post by popperdk on Tue Apr 28, 2015 2:17 am

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

    Sponsored content

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

    Post by Sponsored content Today at 3:40 am


      Current date/time is Tue Dec 06, 2016 3:40 am