Trang 1 trên tổng số 3 123 Cuối cùngCuối cùng
Từ 1 tới 10 trên tổng số 24 kết quả

Đề tài: Bài toán cái ba lô dùng kỹ thuật nhánh cận

  1. #1
    Ngày gia nhập
    10 2008
    Bài viết
    9

    Mặc định Bài toán cái ba lô dùng kỹ thuật nhánh cận

    Mình đang học lập trình C. Ai biết có thể chỉ mình giải thuật về bài toán "Cái ba lô 2 dùng kỹ thuật nhánh cận".
    Nội dung bài toán: cho một cái ba lô có trọng lượng W và n loại đồ vật,mỗi loại đồ vật i có trọng lượng gi, một giá trị vi và một số lượng mi.
    Tìm một cách lựa chọn các đồ vật đựng vào ba lô, chọn đồ vật nào, mỗi loại lấy bao nhiêu sao cho tổng trọng lượng không vượt quá W và tổng giá trị là lớn nhất??

    Cảm ơn nhiều nhe!!!


    Lưu ý: Không Post các câu hỏi vào Box hướng dẫn. lần sau vi phạm sẽ Delete bài viết.
    Đã được chỉnh sửa lần cuối bởi zkday2686 : 10-10-2008 lúc 06:41 PM.

  2. #2
    Ngày gia nhập
    10 2008
    Bài viết
    258

    ebook đây bạn đem về nghiên cứ nhé
    Attached Files Attached Files

  3. #3
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    - Dùng backtracking để chọn đồ, xài 1 mãng boolean( true or false ), để đánh dấu đồ vật, tạo 1 biến điều kiện gọi GIA_TRI_LON_NHAT_NHAN_DUOC, cứ mỗi lần chọn kiểm tra với điều kiện, nếu nhỏ hơn thì chọn tiếp, nếu không thì cắt nhánh đó đi.
    - Google : branch_bound algorithm để tìm và đọc hiểu nó, sau đó rồi cài đặt thử. Cứ viết rồi post lên đây tui sẽ coi lại cho cậu !

  4. #4
    Ngày gia nhập
    10 2008
    Bài viết
    1

    Mình đang cần làm bằng kỹ thuật nhánh Cận

  5. #5
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    Nhánh cận là quay lùi + cắt nhánh -> là cái mà tui đã nói với cậu ở trên. Tập viết đi, tui có code nhưng tui sẽ không cho đâu ! Chịu khó cho tui thấy cậu đã làm gì thì may ra tui suy nghĩ lại !

  6. #6
    Ngày gia nhập
    10 2008
    Bài viết
    9

    Mặc định Bài toán cái ba lô dùng kỹ thuật nhánh cận

    anh ơi! em có ví dụ này: (giải theo kĩ thuật nhánh cận) trọng lượng tối đa của ba lô W=37
    loại sốlượng trọnglượng giátrị đơngiá
    A 03 10 25 2,5
    B 02 15 30 2,0
    C 02 04 06 1,5
    D 02 02 02 1,0

    Ta có nút gốc A bdiễn cho trạng thái chưa chọn đồ vật nào. Khi đó TGT=0; W=37; CT=(3*10)*2,5 + (1*4)*1,5 + (1*2)*1=83
    Với nút B, thì ta có 4 khả năng chọn:
    + chọn 3 đồ vật loại B: khi đó TGT=75; W=7; CT= 75+ 7*2= 89
    + chọn 2 đồ vật loại B: khi đó TGT=50;W=17; CT= 50+ 17*2=84
    + chọn 1 đồ vật loại B: TGT=25; W=27; CT= 79
    + chọn 0 đồ vật loại B: TGT= 0; W=37; CT= 74
    ứng với mỗi trường hợp của B ta tiếp tục chọn với A,D,C.....

    cho em hỏi là em làm vậy có đúng không?? nếu sai thì phải sửa như thế nào??
    tại sao khi chọn 3,2 đồ vật loại B thì CT lại lớn hơn CT của nút gốc?? bài toán ba lô 1 và 3 đều nhỏ hơn!!!!
    Thầy em trong lớp chỉ cho ví dụ bài toán cái ba lô 1 và 3 thôi!!
    em làm ví dụ trước rồi từ từ mới viết giải thuật. Dạo này em còn học, thi nhiều môn nữa nên chưa viết đc!!
    mong các anh trả lời giúp em! em cảm ơn rất nhiều
    Đã được chỉnh sửa lần cuối bởi thaimun : 16-10-2008 lúc 09:19 PM.

  7. #7
    Ngày gia nhập
    10 2008
    Bài viết
    9

    ko ai trả lới giúp mình hết sao??

  8. #8
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    Bài loại 2 của cậu là khó chịu nhất, lâu rồi tui cũng ít làm dạng giải thuật này, nên để mai tui suy nghĩ kĩ lại đã vì bắt tay cài đặt liền tui cũng không dám chắc có làm ra không nữa.
    I'll give it a try tomorrow !

  9. #9
    Ngày gia nhập
    10 2008
    Bài viết
    9

    xin cảm ơn anh trước nhe!!!
    mà ví dụ ở trên em làm đúng ko vậy??

  10. #10
    Ngày gia nhập
    10 2008
    Bài viết
    9

    có ai trả lời giúp mình tí ko??
    mình đang cần gấp

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

  1. Thuật toán fft có thể dùng với số mẫu lẻ được không
    Gửi bởi silkworm trong diễn đàn Thắc mắc CTDL & Giải thuật
    Trả lời: 0
    Bài viết cuối: 22-05-2012, 01:33 AM
  2. Thuật toán sắp xếp dãy số A có độ phức tạp O(n) thì dùng thuật toán nào?
    Gửi bởi maythywinter trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 5
    Bài viết cuối: 16-10-2011, 11:01 PM
  3. Thuật toán trộn 2 mảng thành 1 mảng tăng đàn ko dùng thuật toán sắp xếp
    Gửi bởi caphetim trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 6
    Bài viết cuối: 21-03-2011, 06:40 PM
  4. cho hỏi về thuật toán UCS dùng để tìm kiếm đường đi?
    Gửi bởi vuit trong diễn đàn Thắc mắc lập trình Visual C++
    Trả lời: 0
    Bài viết cuối: 11-04-2010, 01:37 PM
  5. Dùng IDE nào để lập trình thuần C++ với API?
    Gửi bởi mysuncl trong diễn đàn Thắc mắc lập trình Visual C++
    Trả lời: 10
    Bài viết cuối: 28-08-2009, 04:44 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