<h3>Phân loại</h3><ul><li>Bài toán thuộc dạng <strong>tham lam (greedy)</strong> có kiểm tra điều kiện.</li><li>Kết hợp với:<ul><li>Ràng buộc <strong>dãy không giảm</strong></li><li>Ràng buộc <strong>tổng bằng S</strong></li><li>Mỗi vị trí chỉ được chọn từ một <strong>tập giá trị cho trước</strong></li></ul></li></ul><h3>Dấu hiệu nhận biết</h3><p>Các dấu hiệu quan trọng để nhận ra hướng giải:</p><ol><li><strong>D1 ≤ D2 ≤ … ≤ DK</strong><br>→ Dãy <strong>không giảm</strong></li><li><strong>Tổng bằng S</strong><br>→ Không được chọn tùy ý, phải kiểm soát tổng</li><li><strong>Mỗi vị trí i có nhiều lựa chọn khác nhau</strong><br>→ Không phải bài đơn giản, cần chọn khéo</li><li><p><strong>Ưu tiên giá trị nhỏ nhất ở vị trí nhỏ nhất</strong><br>→ Rất rõ dấu hiệu của <strong>tham lam từ trái sang phải</strong></p><p><i><strong>Xây dựng dãy từ trái qua phải, mỗi bước chọn nhỏ nhất nhưng vẫn đảm bảo còn nghiệm phía sau</strong></i></p></li></ol><h3>Ý tưởng</h3><h4>Bước 1: Tiền xử lý</h4><p>Với mỗi vị trí i:</p><ul><li>Lấy tất cả các giá trị do các đoàn đề xuất</li><li>Loại trùng và sắp xếp tăng dần</li></ul><p>→ Gọi tập đó là A[i]</p><h4>Bước 2: Xây dựng dãy bằng tham lam</h4><p>Ta xây lần lượt D1 → DK</p><p>Tại mỗi vị trí i:</p><ul><li>D[i] phải:<ul><li>≥ D[i-1]</li><li>thuộc tập A[i]</li></ul></li><li>Ta thử các giá trị trong A[i] theo thứ tự tăng dần<br>→ chọn giá trị nhỏ nhất <strong>mà vẫn còn khả năng hoàn thành các vị trí phía sau</strong></li></ul><h4>Bước 3: Kiểm tra khả thi</h4><p>Giả sử tại vị trí i, ta thử chọn D[i] = x</p><p>Ta cần kiểm tra với tổng còn lại: remaining = S - (tổng đã chọn + x)</p><p>Có thể chọn các D[i+1] → D[K] sao cho:</p><ul><li>Không giảm</li><li>Tổng đúng bằng remaining</li></ul><h4>Cách kiểm tra</h4><h4>1. Tổng nhỏ nhất có thể đạt</h4><ul><li>Với mỗi vị trí phía sau:<ul><li>chọn giá trị nhỏ nhất nhưng vẫn ≥ giá trị trước</li></ul></li></ul><p>→ tính được <strong>tổng nhỏ nhất</strong></p><h4>2. Tổng lớn nhất có thể đạt</h4><ul><li>Với mỗi vị trí: chọn giá trị lớn nhất → tính được <strong>tổng lớn nhất</strong></li><li>Nếu tổng nhỏ nhất ≤ remaining ≤ tổng lớn nhất→ lựa chọn x là hợp lệ</li></ul>