Từ 1 tới 6 trên tổng số 6 kết quả

Đề tài: Nên dùng thuật toán j cho bài toán tối ưu cắt thép???

  1. #1
    Ngày gia nhập
    05 2010
    Nơi ở
    ha noi
    Bài viết
    2

    Question Nên dùng thuật toán j cho bài toán tối ưu cắt thép???

    - Cho một thanh thép nguyên liệu với chiều dài L (mét). Cần tiến hành cắt thanh thép trên thành các đoạn tiêu chuẩn có chiều dài tương ứng là L1, L2, L3.... Sao cho lượng dư thừa là nhỏ nhất

    Hãy lập chương trình:
    - Nhập giá trị chiều dài thanh thép L:
    - Nhập các chiều dài chuẩn L1, L2, L3,...
    - Tính số lượng các thanh chuẩn có thể được cắt sao cho phần dư nhỏ nhất. ( số lượng thanh >= 0 cho mỗi loại)
    "L1 ,L2 ,L3 là số nguyên "


    Các cao nhân giúp e cần dùng thuật toán j để giải quyết bài này ( giải quyết mấy vẫn đề in đậm chữ nghiêng ý ạ )
    bôi đen làm jề

  2. #2
    Ngày gia nhập
    01 2011
    Nơi ở
    -Mountain-
    Bài viết
    768

    Trích dẫn Nguyên bản được gửi bởi ankkoh Xem bài viết
    - Cho một thanh thép nguyên liệu với chiều dài L (mét). Cần tiến hành cắt thanh thép trên thành các đoạn tiêu chuẩn có chiều dài tương ứng là L1, L2, L3.... Sao cho lượng dư thừa là nhỏ nhất

    Hãy lập chương trình:
    - Nhập giá trị chiều dài thanh thép L:
    - Nhập các chiều dài chuẩn L1, L2, L3,...
    - Tính số lượng các thanh chuẩn có thể được cắt sao cho phần dư nhỏ nhất. ( số lượng thanh >= 0 cho mỗi loại)
    "L1 ,L2 ,L3 là số nguyên "


    Các cao nhân giúp e cần dùng thuật toán j để giải quyết bài này ( giải quyết mấy vẫn đề in đậm chữ nghiêng ý ạ )
    Mình ví dụ thế này xem bạn làm thế nào
    Giả sử có 10m dây. l1 = 4, l2 = 3, l3 = 2, l4 = 1.

    - Để phần dư nhỏ nhất suy ra ta phải cắt theo l lớn nhất -> l1
    tối đa ta cắt đc 2 cái l1 -> Thừa 2 m < 3 -> loại (vì số lượng mỗi loại > 0)

    - Quay lại bước cắt l1 - > được 1 cái l1 và còn thừ 6m
    - Cắt theo l2 - > được 2 sợi l2 nữa -> thiếu l3 và l1 - > loại > quay lại bước cắt l2
    - Cắt được 1 sợi l2 và còn 3 m dây nữa

    -----------> còn 1 sợi l3 và 1 sợi l4 nữa - > đã cắt xong
    Hướng dẫn C++: https://www.youtube.com/watch?v=BwLodoQdoY4&list=PL1c9Uxlo-mplJDRGdONNupgo5OCBTyGGn

  3. #3
    Ngày gia nhập
    09 2009
    Nơi ở
    Hoa sơn tuyệt đỉnh
    Bài viết
    407

    1. Nếu L<10000 thì dùng QHĐ như trong sách của thầy Hoàng
    2. Nếu L>10000 thì tham đến khi L<10000 rồi thực hiện bước 1

    my houses
    my school
    tỐnG lÊ cHâN mAnG kỶ nIệM bUồN cHo AnH...

  4. #4
    Ngày gia nhập
    07 2011
    Bài viết
    160

    Trích dẫn Nguyên bản được gửi bởi ankkoh Xem bài viết
    - Cho một thanh thép nguyên liệu với chiều dài L (mét). Cần tiến hành cắt thanh thép trên thành các đoạn tiêu chuẩn có chiều dài tương ứng là L1, L2, L3.... Sao cho lượng dư thừa là nhỏ nhất

    Hãy lập chương trình:
    - Nhập giá trị chiều dài thanh thép L:
    - Nhập các chiều dài chuẩn L1, L2, L3,...
    - Tính số lượng các thanh chuẩn có thể được cắt sao cho phần dư nhỏ nhất. ( số lượng thanh >= 0 cho mỗi loại)
    "L1 ,L2 ,L3 là số nguyên "


    Các cao nhân giúp e cần dùng thuật toán j để giải quyết bài này ( giải quyết mấy vẫn đề in đậm chữ nghiêng ý ạ )
    Bài này với L không quá lớn (LMAX <= 10000 chẳng hạn) thì có thể dùng quy hoạch động
    Quy ước: LL là độ dài thanh nguyên liệu
    n là số lượng thanh chuẩn. L[1] -> L[n] là độ dài các thanh chuẩn (L[i] nguyên dương)
    Ta sẽ lập mảng a[] với ý nghĩa như sau:
    a[x] = i (1 <= x <= LL) nếu tồn tại 1 cách cắt thanh nguyên liệu chiều dài x thành các thanh chuẩn, và thanh chuẩn cuối cùng được cắt ra có số hiệu là i (1 <= i <= n).
    a[x] = 0 nếu không tồn tại cách cắt như trên.

    C++ Code:
    1. #define LMAX 10000
    2. int a[LMAX] = {1};
    3. for (int l1 = 0; l1 < LL; ++l1) {
    4.     if (a[l1] == 0) continue;    // không có cách cắt độ dài l thành các thanh chuẩn
    5.     for (int i = 1; i <= n; ++i) {
    6.         int l2 = l1 + L[i];
    7.         if (l2 <= LL && a[l2] == 0) a[l2] = i;
    8.     }
    9. }

    Sau bước này, các chiều dài có thể cắt được thành các thanh chuẩn đã được lưu vào mảng a. Tìm phần dư nhỏ nhất rất đơn giản:
    C++ Code:
    1. int lmax;
    2. for (lmax = LL; lmax > 0; --lmax)
    3.     if (a[lmax] > 0) break;
    Sau bước này ta đã có lmax là chiều dài tối đa có thể cắt thành các thanh chuẩn (nói cách khác, phần dư là LL - lmax). Bây giờ phải đếm xem đã cắt ra bao nhiêu thanh chuẩn mỗi loại:

    C++ Code:
    1. int count[N + 1] = {0};
    2. while (lmax > 0) {
    3.     int i = a[lmax];
    4.     ++count[i];
    5.     lmax -= L[i];
    6. }

    Xong

  5. #5
    Ngày gia nhập
    05 2010
    Nơi ở
    ha noi
    Bài viết
    2

    Trích dẫn Nguyên bản được gửi bởi beautifulsoul84hung Xem bài viết
    Mình ví dụ thế này xem bạn làm thế nào
    Giả sử có 10m dây. l1 = 4, l2 = 3, l3 = 2, l4 = 1.

    - Để phần dư nhỏ nhất suy ra ta phải cắt theo l lớn nhất -> l1
    tối đa ta cắt đc 2 cái l1 -> Thừa 2 m < 3 -> loại (vì số lượng mỗi loại > 0)

    - Quay lại bước cắt l1 - > được 1 cái l1 và còn thừ 6m
    - Cắt theo l2 - > được 2 sợi l2 nữa -> thiếu l3 và l1 - > loại > quay lại bước cắt l2
    - Cắt được 1 sợi l2 và còn 3 m dây nữa

    -----------> còn 1 sợi l3 và 1 sợi l4 nữa - > đã cắt xong
    cảm ơn bạn nhưng đề bài số lượng mỗi loại có thể >= 0 bạn ah !
    bôi đen làm jề

  6. #6
    Ngày gia nhập
    07 2011
    Nơi ở
    hà nội
    Bài viết
    11

    Mặc định Nên dùng thuật toán j cho bài toán tối ưu cắt thép???

    Trích dẫn Nguyên bản được gửi bởi ankkoh Xem bài viết
    cảm ơn bạn nhưng đề bài số lượng mỗi loại có thể >= 0 bạn ah !
    nếu vậy bạn chỉ việc tìm số dư nhỏ nhất của phép chia L/Li(i = 1, 2,3...) là xong

Các đề tài tương tự

  1. Nên dùng cơ sở dữ liệu nào vào lập trình web bằng ASP.NET
    Gửi bởi tuanvu199x trong diễn đàn Thắc mắc lập trình ASP.NET
    Trả lời: 8
    Bài viết cuối: 24-09-2011, 11:40 AM
  2. Nên nên chọn đề tài nào để làm đề án dùng c# + csdl
    Gửi bởi chitvivo trong diễn đàn Nhập môn lập trình C#, ASP.NET
    Trả lời: 23
    Bài viết cuối: 18-09-2011, 12:57 AM
  3. soft bị treo do vòng for xử lý quá nhiều, có nên dùng kĩ thuật đa luồng
    Gửi bởi chitvivo trong diễn đàn Thắc mắc lập trình C#
    Trả lời: 13
    Bài viết cuối: 30-08-2011, 05:31 PM
  4. Nén 1 xâu còn 25% độ dài, nên dùng thuật toán nào?
    Gửi bởi longtth trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 3
    Bài viết cuối: 24-08-2011, 11:01 AM
  5. Đếm kí tự, nên dùng hàm gì?
    Gửi bởi killzone266 trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 3
    Bài viết cuối: 06-10-2009, 06:08 PM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn