VẬN DỤNGCácbức ảnhTrong một hoạt động ngoại khóa của lớp, giáo viên chủ nhiệm đã chụp được n...
VẬN DỤNG
Các bức ảnh
Trong một hoạt động ngoại khóa của lớp, giáo viên chủ nhiệm đã chụp được n bức ảnh, các bức ảnh được lưu trên máy tính có kích thước tương ứng là d1 , d2 , ..., dn , (đơn vị Kb).
Giáo viên dự định ghi một số đĩa CD làm phần thưởng cho học sinh. Đĩa CD mà giáo viên dùng chỉ có thể ghi tối đa W (đơn vị Kb). Vì tất cả các bức ảnh đều rất đẹp và thú vị nên giáo viên muốn lựa chọn các bức ảnh để ghi vào đĩa CD với tiêu chí càng nhiều bức ảnh được ghi vào địa CD càng tốt. Giáo viên băn khoăn và muốn biết số lượng tối đa các bức ảnh có thể ghi vào đĩa CD là bao nhiêu.
Em hãy chỉ ra kết quả từng bước thực hiện để có được chương trình nhận dữ liệu vào là các số nguyên W, d1 , d2 , ..., dn à trả về số lượng tối đa các bức ảnh có thể ghi vào đĩa CD.
Dưới đây là mã giả của thuật toán:
1. Nhập dữ liệu W, và dữ liệu list d có độ dài n.
2. Sắp xếp list d theo thứ tự tăng dần.
3. Khởi tạo biến s = 0 là tổng dung lượng ảnh đã chọn, biến c = 0 là số ảnh được chọn.
4. Duyệt từng bức ảnh trong list d:
- Nếu s + d[i] <= W, thì tăng s lên d[i] và tăng c lên 1.
5. Kết thúc và in ra số ảnh c được chọn.
Ví dụ: giả sử W = 1000 Kb và list d = [400, 200, 300, 600, 800] Kb.
Sắp xếp list d: [200, 300, 400, 600, 800]
Duyệt từng bức ảnh:
- Chọn bức ảnh có kích thước 200 Kb, s = 200, c = 1
- Chọn tiếp bức ảnh có kích thước 300 Kb, s = 500, c = 2
- Không chọn bức ảnh có kích thước 400 Kb vì s + 400 > 1000, s = 500, c = 2
- Chọn bức ảnh có kích thước 600 Kb, s = 1100, c = 3 (vượt quá dung lượng W)
- Kết thúc, số ảnh c được chọn là 2.
Đáp án: Số lượng tối đa các bức ảnh có thể ghi vào đĩa CD là 2.