Mỗi quả cân 1,2,4,8 carat tương ứng với các bit nhị phân (1,2,4,8). Mỗi lần cân kiểm tra một viên kim cương có khối lượng \(w \in \left{\right. 1 , \ldots , 15 \left.\right}\) ta chỉ được đặt các quả cân ở bên kia sao cho tổng bằng \(w\). Nếu một quả cân được giữ liên tiếp trong nhiều lần cân thì ta chỉ phải trả một lần cho khoảng thời gian liên tiếp đó; nếu nó bị lấy ra rồi sau đó dùng lại thì phải mượn và trả thêm lần nữa. Vấn đề là sắp xếp thứ tự các lần cân (các giá trị 1..15) để tổng số “lần bắt đầu sử dụng” (mỗi lần như vậy tốn 100 đồng) của 4 quả cân là nhỏ nhất. Ta có thể mô hình hoá và tìm thứ tự tối ưu; tổng số lần bắt đầu sử dụng tối thiểu là 8 → chi phí \(8 \times 100 = 800\) đồng.
Một thứ tự cân đạt chi phí 800 đồng (mỗi lần đặt một viên lên 1 bên, các quả cân ở bên kia):
Thứ tự các trọng lượng kim cương cân:8, 10, 14, 12, 13, 9, 11, 15, 7, 5, 4, 6, 2, 3, 1
Với mỗi bước ghi rõ các quả cân (1,2,4,8) cần đặt trên bên kia:
- 8 → đặt
{8} - 10 → đặt
{8,2} - 14 → đặt
{8,4,2} - 12 → đặt
{8,4} - 13 → đặt
{8,4,1} - 9 → đặt
{8,1} - 11 → đặt
{8,2,1} - 15 → đặt
{8,4,2,1} - 7 → đặt
{4,2,1} - 5 → đặt
{4,1} - 4 → đặt
{4} - 6 → đặt
{4,2} - 2 → đặt
{2} - 3 → đặt
{2,1} - 1 → đặt
{1}
Các lần mượn mới (tóm tắt):
- quả cân 8: chỉ cần mượn 1 lần (tổng 100)
- quả cân 4: mượn 2 lần (tổng 200)
- quả cân 2: mượn 3 lần (tổng 300)
- quả cân 1: mượn 2 lần (tổng 200)
Tổng = \(100 + 200 + 300 + 200 = 800\) đồng.
