Đến nội dung


Chú ý

Nếu các bạn đăng kí thành viên mà không nhận được email kích hoạt thì hãy kiểm tra thùng thư rác (spam). Nếu không biết cách truy cập vào thùng thư rác thì các bạn chịu khó Google hoặc đăng câu hỏi vào mục Hướng dẫn - Trợ giúp để thành viên khác có thể hỗ trợ.


Hình ảnh

Hãy xác định giá trị M nhỏ nhất là bao nhiêu?


  • Please log in to reply
Chưa có bài trả lời

#1 Nam Antoneus

Nam Antoneus

    Hạ sĩ

  • Thành viên
  • 61 Bài viết
  • Giới tính:Nam
  • Đến từ:THPT Lương Thế Vinh
  • Sở thích:Trinh thám

Đã gửi 21-03-2017 - 09:28

      Atêna, đứa con được thần Dớt sinh ra từ đầu của mình, là một vị nữ thần của Trí tuệ, Tri thức và Chiến trận. Nàng đã sáng tạo ra N loại bảo bối khác nhau. Bảo bối thứ i trọng lượng wi và sức mạnh chiến đấu là pi (i N =1.. ) . Số lượng mỗi loại bảo bối là không hạn chế.

 

     Trước mỗi trận chiến, để giành được chiến thắng, Atêna cần chọn M bảo bối để mang theo sao cho tổng trọng lượng đúng bằng W và tổng sức mạnh đúng bằng P . Nếu không chọn được thì trận chiến được hoãn lại và khi đó M được đặt bằng 0.

Yêu cầu: Hãy xác định giá trị M nhỏ nhất là bao nhiêu?
Dữ liệu: Đọc vào từ tệp văn bản WPM.INP có cấu trúc như sau:

        - Dòng đầu ghi lần lượt ba số n, p, w (0 < n < 21;0 < p, w <150) ;

        - N dòng tiếp theo, dòng thứ i ghi lần lượt hai số Pi W(0 < Pi , W<150) ;

        - Các số trên cùng một dòng cách nhau một dấu cách.
Kết quả: Ghi ra tệp văn bản WPM.OUT gồm một số duy nhất là giá trị M tìm được.

Ví dụ:  WPM.INP      WPM.INP
            3 11 17              0
            12 3
            4 7
            8 10
            WPM.INP      WPM.INP
            4 9 17                4
            1 2
            2 3
            3 6
            4 10
Phương án tối ưu trong ví dụ trên được thực hiện như sau:
- chọn bảo bối thứ 1 với số lượng 1 cái có được sức mạnh 1 và trọng lượng 2;
- chọn bảo bối thứ 2 với số lượng 1 cái có được sức mạnh 2 và trọng lượng 3;
- chọn bảo bối thứ 3 với số lượng 2 cái có được sức mạnh 6 và trọng lượng 12.






0 người đang xem chủ đề

0 thành viên, 0 khách, 0 thành viên ẩn danh