Khởi nghiệp | Đề thi HSG tin 12 Nghệ An | năm học 2022 - 2023

Ban đầu, Đức chưa hợp tác được với công ty nào. Hãy tính chi phí ít nhất để Đức có thể hợp tác với tất cả n công ty. Dữ liệu cho trong file văn bản KhoiNghiep.Inp gồm:

• Dòng 1 ghi số nguyên dương n là số công ty.

• n dòng tiếp theo, dòng thứ i ghi hai số nguyên ai,bi (1≤i≤n;0≤ai ≤n; 0 ≤bi ≤10^4)

Kết quả ghi ra file văn bản KhoiNghiep.Out gồm một số nguyên duy nhất là chi phí ít nhất để Đức có thể hợp tác với tất cả n công ty.

Giải:

# Đọc dữ liệu từ file input with open("KhoiNghiep.Inp", "r") as f: n = int(f.readline().strip()) companies = [] for i in range(n): a, b = map(int, f.readline().strip().split()) companies.append((a, b)) # Sắp xếp các công ty theo giá trị bi tăng dần companies.sort(key=lambda x: x[1]) # Khởi tạo danh sách công ty đã hợp tác partnered = [False] * n e = 0 total_cost = 0 i = 0 for i in range(n): if not partnered[i]: if e >= companies[i][0]: # Kiểm tra công ty đang xét có free không nếu đuợc thì vào. partnered[i] = True e += 1 else: # Kiểm tra các công ty còn lại có được free không. j = i + 1 while j < n: if e >= companies[j][0] and not partnered[j]: partnered[j] = True e += 1 j = i # Nếu được vào free thì kiểm tra lại từ i đến hết vì e đã thay đổi. continue else: j += 1 if not partnered[i]: # Thoát khỏi vòng while nên không còn có công ty hợp tác free nữa. total_cost += companies[i][1] partnered[i] = True e += 1 with open('KhoiNghiep.Out', 'w') as f: f.write(str(total_cost))

Giải thích:

Trong đoạn code trên, ta sử dụng một vòng lặp while để kiểm tra từng công ty. Nếu công ty đó đã được hợp tác, ta tăng giá trị của i lên 1 và tiếp tục kiểm tra công ty tiếp theo. Nếu công ty đó chưa được hợp tác, ta kiểm tra xem có thể hợp tác free hay không. Nếu có, ta đánh dấu công ty đó đã hợp tác và kiểm tra trong các công ty chưa được hợp tác xem còn công ty nào có thể hợp tác free không. Nếu không có, ta tìm công ty có giá trị bi nhỏ nhất để hợp tác. Nếu không có công ty nào có thể hợp tác, ta tăng tổng chi phí lên giá trị bi của công ty hiện tại và đánh dấu công ty đó đã hợp tác.

Thuật toán mà tôi đã sử dụng để giải quyết bài toán này là một phương pháp tham lam. Cụ thể, ta sẽ kiểm tra từng công ty để xem có thể hợp tác free không. Nếu không thể hợp tác free, ta giải quyết bài toán bằng cách tìm công ty có giá trị bi nhỏ nhất để hợp tác.

Thuật toán này được gọi là phương pháp tham lam vì ta luôn chọn công ty có giá trị bi nhỏ nhất để hợp tác, mà không đánh giá tác động của quyết định đó đến việc hợp tác với các công ty khác ở những bước sau. Tuy nhiên, trong bài toán này, phương pháp tham lam này lại cho kết quả chính xác, mà không cần tìm cách tối ưu toàn bộ quy trình hợp tác.