kết quả từ 1 tới 4 trên 4

bài tập áp dụng thuật toán sắp xếp mọi người cho ý kiến

  1. #1
    Ðến Từ
    Quảng Bình
    Thành Viên Thứ: 333805
    Giới tính: Nam
    Bài gửi
    62

    bài tập áp dụng thuật toán sắp xếp mọi người cho ý kiến

    Bài 3: (7 điểm) CHỌN PHẦN THƯỞNG
    Trong kỳ thi học sinh giỏi môn Tin học, em là người đạt giải đặc biệt. Ban tổ chức cho phép em chọn các phần thưởng cho mình. Các phần thưởng xếp thành một dãy được đánh số từ 1 đến N (0 ≤ N ≤ 10000), phần thưởng thứ i có giá trị là ai (1 ≤ ai ≤ 100). Em được phép chọn các phần thưởng cho mình theo nguyên tắc không chọn 3 phần thưởng liên tiếp nhau trong dãy.
    Viết chương trình để máy tính hướng dẫn em chọn các phần thưởng sao cho tổng giá trị của các phần thưởng nhận được là lớn nhất.
    Dữ liệu vào: cho file PTHUONG.INP gồm các dòng:

    - Dòng đầu tiên là số phần thưởng N

    - N dòng tiếp theo lần lượt là giá trị của các phần thưởng.

    Dữ liệu ra: ghi ra file PTHUONG.OUT gồm các dòng:

    - Dòng đầu tiên ghi tổng giá trị lớn nhất của các phần thưởng đã chọn

    - Dòng tiếp theo ghi vị trí của các phần thưởng đã chọn theo thứ tự tăng dần.

    Ví dụ:


    PTHUONG.INP PTHUONG.OUT
    5
    6
    9
    1
    3
    5
    23
    1 2 4 5


    Hoặc

    PTHUONG.INP PTHUONG.OUT
    7
    6
    9
    1
    3
    5
    10
    4
    32
    1 2 4 6 7
    Quick reply to this message Trả lời       


  2. #2
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    881

    Reply: bài tập áp dụng thuật toán sắp xếp mọi người cho ý kiến

    Bài này chính là bài "Bờm uống rượu" mình đã giải ở trong thread này. Bạn tham khảo từ post #4 nhé.
    Mã:
    http://vforum.vn/diendan/showthread.php?93411-Giai-giup-minh-bai-nay-bang-Quy-Hoach-Dong-voi
    Có gì không hiểu bạn cứ hỏi.
    LCD: 13.3" 1920x1080 IPS
    CPU: Intel i7 - 4700MQ (2.4 GHz - 3.4 GHz)
    GPU: Nvidia GTX 765m with GDDR5 2GB
    RAM: 2x8GB G.Skill 2133
    HDD: Samsung SSD 850 Pro 512 GB
    2 kg.

  3. Đã cảm ơn tengiday:


  4. #3
    Ðến Từ
    Quảng Bình
    Thành Viên Thứ: 333805
    Giới tính: Nam
    Bài gửi
    62

    Reply: bài tập áp dụng thuật toán sắp xếp mọi người cho ý kiến

    Với bài này nhờ bạn nói rõ cách giải ko bằng qhd cho mình với dk ko ak..
    và nếu cách ko làm bằng qhd này thì bài toán làm theo cách nào sẽ tôi ưu hơn vậy bạn

  5. Đã cảm ơn vansonqtqb:


  6. #4
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    881

    Reply: bài tập áp dụng thuật toán sắp xếp mọi người cho ý kiến

    Mình có thể khẳng định với bạn, với bài này thì quy hoạch động là thuật toán tối ưu nhất. Độ phức tạp của thuật toán là O(n), bằng với kích cỡ của dữ liệu. Theo như thuật toán, tương đương như chúng ta chỉ cần đọc dữ liệu 2 lần là cho ra kết quả vậy (1 lần tạo F và 1 lần truy ngược). Trừ khi có cách ko cần đọc hết dữ liệu vẫn biết kết quả thì mới nhanh hơn đc, nhưng mình không nghĩ ra cách nào như vậy bởi vì ít nhất chúng ta phải đọc file toàn bộ n số mà.
    Nếu ko dùng qhđ thì thô thiển nhất là dùng đệ quy quay lui để duyệt toàn bộ khả năng chọn, sau đó lựa ra sự lựa chọn đạt giá trị lớn nhất. Tuy nhiên, n có thể tới 10000, cách làm này chính là duyệt toàn bộ tổ hợp có thể lên tới ít nhất hàng trăm triệu (mình ko tính chính xác đc vì mình dở xác suất lắm).

  7. 2 thành viên đã cảm ơn tengiday: