• #1
    Tham gia
    12-03-2010
    Bài viết
    9
    Like
    0
    Thanked 1 Time in 1 Post

    bài toán về mảng 2 chiều

    Trong một phân xưởng sản xuất, để hoàn thành được 1 sản phẩm, người quản đốc phải sử dụng n công nhân để gia công n chi tiết. Biết rằng công sức để gia công 1 chi tiết của mỗi công nhân là như nhau. Người ta sử dụng mảng 2 chiều C gồm n hàng và n cột biểu diễn chi phí gia công của công nhân cho từng chi tiết cụ thể, trong đó giá trị C[i,j] là số công bỏ ra của công nhân thứ i gia công chi tiết j. (1 . C[i,j] . 20000)
    Yêu cầu: Tìm tổng số công nhỏ nhất của toàn bộ các công nhân để hoàn thành n chi tiết sao cho mỗi công nhân chỉ gia công đúng một chi tiết.
    INPUT:
    dòng đầu ghi số nguyên n (1. n . 20) là số lượng công nhân và số chi tiết
    trong n hàng tiếp theo, mỗi hàng biểu diễn n giá trị (được ngăn cách với nhau bởi dấu trống) thể hiện số công bỏ ra của công nhân thứ i cho n chi tiết tương ứng.
    OUTPUT:
    ghi tổng số công nhỏ nhất của mọi ng để hoàn thành n chi tiết trên sao cho mỗi ng chỉ đc gia công 1 chi tiết
    Ví dụ
    INPUT:
    3
    4 5 7
    3 6 8
    7 8 8
    OUTPUT:
    16
    ai giúp e làm bài này theo quay lui nhé. E tks nhiều
    Quote Quote

  • #2
    Tham gia
    26-10-2012
    Bài viết
    180
    Like
    35
    Thanked 19 Times in 19 Posts
    mình code tay nêu ý tưởng thôi nhé, có gì bạn code thêm vào, chứ mình không viết hẳn ra đâu
    ý tưởng là thế này.
    bạn duyệt từ sản phẩm 1 đến sản phẩm thứ n, ở mỗi sản phẩm bạn thử cho tất cả các công nhẩn thử làm sản phẩm đó, nếu công nhân đó chưa làm sản phẩm nào trước đó và chi phí công nhân đó bỏ ra cho sản phẩm thứ i cộng vs chi phí thực hiện các sản phẩm trc đó nhỏ hơn chi phí nhỏ nhất để làm tất cả các sản phẩm hiện tại thì chọn công nhân đó thực hiện sản phẩm i.
    cứ làm như vậy cho đến khi đến sản phẩm thứ n thì dừng lại.
    var a: array[....] of ...;
    free: array[1..n] of integer;
    longint min;
    procedure nhap;
    procedure try(integer k, total)
    var integer i;
    begin
    for i:= 1 to n do
    if (free[i] = 0) and (total + a[i,k] < min) then
    begin
    minp:= minp + a[i,k];
    free[i]:= 1;
    if i < n then try(k+1, minp)
    else
    min = total;
    free[i]:= 0;
    end;
    end;
    begin
    Input; bạn tự viết
    min = 1000000000;
    fillchar(free,sizeof(free),0)
    Try(1, 0);
    Output; bạn tự viết
    end.

  • #3
    Tham gia
    26-10-2012
    Bài viết
    180
    Like
    35
    Thanked 19 Times in 19 Posts
    mình code tay nêu ý tưởng thôi nhé, có gì bạn code thêm vào, chứ mình không viết hẳn ra đâu
    ý tưởng là thế này.
    bạn duyệt từ sản phẩm 1 đến sản phẩm thứ n, ở mỗi sản phẩm bạn thử cho tất cả các công nhẩn thử làm sản phẩm đó, nếu công nhân đó chưa làm sản phẩm nào trước đó và chi phí công nhân đó bỏ ra cho sản phẩm thứ i cộng vs chi phí thực hiện các sản phẩm trc đó nhỏ hơn chi phí nhỏ nhất để làm tất cả các sản phẩm hiện tại thì chọn công nhân đó thực hiện sản phẩm i.
    cứ làm như vậy cho đến khi đến sản phẩm thứ n thì dừng lại.
    var a: array[....] of ...;
    free: array[1..n] of integer;
    longint min;
    procedure nhap;
    procedure try(integer k, total)
    var integer i;
    begin
    for i:= 1 to n do
    if (free[i] = 0) and (total + a[i,k] < min) then
    begin
    minp:= minp + a[i,k];
    free[i]:= 1;
    if i < n then try(k+1, total)
    else
    min = total;
    free[i]:= 0;
    end;
    end;
    begin
    Input; bạn tự viết
    min = 1000000000;
    fillchar(free,sizeof(free),0)
    Try(1, 0);
    Output; bạn tự viết
    end.

  • Chưa có bình luận nào, bạn hãy là người đầu tiên bình luận cho bài viết này.
    Bạn cần Đăng nhập để bình luận bài viết
    ĐĂNG KÝ THIẾT KẾ

    CHAT VỚI

    X HOME - THINKDIFFERENTLY * NGÔI NHÀ ĐẶC BIỆT - SUY NGHĨ KHÁC BIỆT chuyên thiết kế, thi công xây dựng, nội thất, sơn bả thạch cao, mỹ thuật, sân vườn tiểu cảnh, cây cảnh, cây công trình. Hotline: 0965.163.169 - 0975.163.169 - 0949.163.169 - 0902.112.114 - 0915.511.577