Cho 5 đồ dùng với giá và mức độ yêu thích tương ứng như trong Bảng 1. Nếu T= 20 (nghìn đồng

149

Với giải Hoạt động 1 trang 55 Chuyên đề Tin học 11 Cánh diều chi tiết trong Bài 2: Kĩ thuật quay lui giúp học sinh dễ dàng xem và so sánh lời giải từ đó biết cách làm bài tập Chuyên đề Tin học 11. Mời các bạn đón xem:

Giải bài tập Chuyên đề Tin học 11 Bài 2: Kĩ thuật quay lui

Hoạt động 1 trang 55 Chuyên đề Tin học 11Cho 5 đồ dùng với giá và mức độ yêu thích tương ứng như trong Bảng 1. Nếu T= 20 (nghìn đồng) thì Hồng cần chọn mua những đồ dùng nào để tổng mức độ yêu thích là lớn nhất?

Cho 5 đồ dùng với giá và mức độ yêu thích tương ứng như trong Bảng 1

Lời giải:

Lời giải bài toán này có thể biểu diễn bằng 1 dãy bit độ dài n (n là số lượng đồ vật), trong đó bit thứ i (0 ≤ i ≤ n - 1) bằng 1 hoặc 0 tương ứng là vật thứ i được chọn hoặc không chọn

Ví dụ: dãy bit (1, 0, 0, 1, 0) tương ứng với cách chọn đồ dùng số 0 và 3 với tổng giá là 10 +9 = 19 (nghìn đồng) và mức độ yêu thích là 7 + 6 = 13; dãy bit (1, 1, 0, 0, 1) tương ứng với cách chọn đồ dùng số 0, 1 và 4 có tổng giá là 10 + 5 + 5 = 20 (nghìn đồng) và mức độ yêu thích là 7 + 2 + 3 = 12.

Để giải quyết bài toán Mua đồ tổng quát bằng kĩ thuật duyệt ta có thể xét toàn bộ dãy bit độ dài n, với mỗi dãy bit tương ứng với một phương án mua, ta tiến hành tính tổng giá để kiểm tra ràng buộc không vượt quá T (đồng) và tính tổng mức độ yêu thích đề chọn phương án tối ưu.

Đánh giá

0

0 đánh giá