Một công ty sản xuất thiết bị công nghệ thông tin có 3 phân xưởng sản xuất thiết bị A, B, C. Công ty mới tuyển thêm N nhân viên (N chia hết cho 3), mỗi nhân viên được đánh số thứ tự từ 1 đến N. Mỗi nhâ...

Bài toán này là một bài toán phân phối nhân viên vào 3 phân xưởng sao cho mỗi phân xưởng có đúng N/3 nhân viên và tổng lợi nhuận là lớn nhất. Đây là bài toán tối ưu kết hợp, có thể giải bằng phương pháp quay lui (backtracking) với cắt tỉa hoặc dùng quy hoạch động (DP) với trạng thái lưu số lượng nhân viên đã phân cho từng phân xưởng. Dưới đây là hướng tiếp cận và code mẫu C++ giải bài toán: **Ý tưởng:** - Có N nhân viên, mỗi nhân viên có 3 lựa chọn phân xưởng A, B, C. - Mỗi phân xưởng phải có đúng N/3 nhân viên. - Ta sẽ dùng đệ quy để thử phân công nhân viên thứ i vào A, B hoặc C nếu còn chỗ. - Lưu lại lợi nhuận tối đa thu được. - Vì N tối đa 24, nên N/3 = 8, số trạng thái không quá lớn để giải bằng backtracking có cắt tỉa. --- **Code C++ mẫu:** ```cpp #include <bits> using namespace std; int N; int A[25], B[25], C[25]; int n3; // N/3 int maxProfit = 0; void backtrack(int i, int countA, int countB, int countC, int currentProfit) { if (i == N) { if (countA == n3 && countB == n3 && countC == n3) { maxProfit = max(maxProfit, currentProfit); } return; } // Nếu còn chỗ cho A if (countA < n3) { backtrack(i + 1, countA + 1, countB, countC, currentProfit + A[i]); } // Nếu còn chỗ cho B if (countB < n3) { backtrack(i + 1, countA, countB + 1, countC, currentProfit + B[i]); } // Nếu còn chỗ cho C if (countC < n3) { backtrack(i + 1, countA, countB, countC + 1, currentProfit + C[i]); } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); freopen("JOB.INP", "r", stdin); freopen("JOB.OUT", "w", stdout); cin >> N; n3 = N / 3; for (int i = 0; i < N; i++) { cin >> A[i] >> B[i] >> C[i]; } backtrack(0, 0, 0, 0, 0); cout << maxProfit << "\n"; return 0; } ``` --- **Giải thích:** - Hàm `backtrack` thử phân công nhân viên thứ i vào A, B hoặc C nếu còn chỗ. - Khi i == N, kiểm tra xem đã đủ số lượng nhân viên cho mỗi phân xưởng chưa, nếu đủ thì cập nhật lợi nhuận tối đa. - Kết quả in ra file JOB.OUT là lợi nhuận tối đa. Bạn có thể chạy thử với dữ liệu ví dụ: ``` 3 30 10 27 11 4 10 12 10 5 ``` Kết quả sẽ là 47 như yêu cầu. Nếu cần tối ưu hơn, có thể dùng memo hoặc DP nhưng với N <= 24, cách này đủ nhanh.