Phân tích: Candy Store

Tóm tắt

Lúc đầu, bài toán này có vẻ khá đáng sợ. Có rất nhiều cách khách hàng có thể đặt hàng, và ngay cả khi bạn đã quyết định chọn những hộp nào, việc xác minh rằng tất cả các tình huống có thể xảy ra đều được đáp ứng là điều không hề đơn giản.

Nhưng hóa ra, một thuật toán tham lam để chọn các hộp và một cách tiếp cận tham lam để đưa chúng cho khách hàng lại hoạt động hiệu quả! Và cũng giống như hầu hết các bài toán tham lam, khó khăn chỉ nằm ở việc thuyết phục bản thân rằng nó đúng. Đây thực sự là bài toán dễ cài đặt nhất trong bộ đề. Điều duy nhất bạn phải vượt qua là sự nghi ngờ bản thân!

Chứng minh

Giả sử một phần đơn hàng của chúng ta là một tập hợp các hộp có tổng trọng lượng \(N\) gam, không có hộp nào lớn hơn \(X = \lfloor N/k \rfloor + 1\). Hơn nữa, giả sử chúng ta biết các hộp này có tính chất là nếu tổng đơn hàng của \(k\) khách hàng không quá \(N\) gam, các hộp này có thể được sử dụng một cách tham lam để đáp ứng đơn hàng của họ. "Tham lam" ở đây nghĩa là khi một khách hàng đến cửa hàng, bạn chỉ cần tìm hộp lớn nhất nhỏ hơn hoặc bằng đơn hàng của họ và đưa cho họ, lặp lại cho đến khi bạn đáp ứng chính xác đơn hàng đó. Đây là giả thuyết quy nạp của chúng ta: một sự đảm bảo rằng chiến lược này hoạt động.

Bây giờ, giả sử chúng ta đặt thêm một hộp nữa có trọng lượng \(X\) (tức là \(\lfloor N/k \rfloor + 1\)) gam, tạo thành một tập hợp các hộp mới có tổng trọng lượng \(N+X\) gam (và lưu ý rằng không có hộp nào lớn hơn \(\lfloor (N+X)/k \rfloor + 1\), điều này là hiển nhiên). Giả sử \(k\) khách hàng đặt hàng không quá \(N+X\) gam. Điều gì xảy ra nếu chúng ta áp dụng chiến lược tham lam? À, ngay khi chúng ta thấy một đơn hàng \(\ge X\) xu, chúng ta sẽ sử dụng ngay hộp \(X\) gam mới này cho nó. Nếu bây giờ chúng ta giả vờ rằng khách hàng đó đã đặt ít đi \(X\) xu, thì chúng ta biết chiến lược tham lam với các hộp còn lại sẽ hoạt động. Các lựa chọn được đưa ra bởi chiến lược này không thay đổi ngoại trừ việc sử dụng hộp mới. Nếu hóa ra KHÔNG có đơn hàng nào \(\ge X\) xu, thì tổng cộng tối đa là \(k \times (X-1) \le k \times (N/k) = N\) gam. Hộp mới không bao giờ có thể được sử dụng, vì vậy chiến lược tham lam thực hiện cùng một việc cho các đơn hàng này như trước đó, và do đó nó hoạt động.

Vì vậy, bằng cách sử dụng quy nạp, giờ đây chúng ta có cái mà tôi gọi là "Thuật toán", dùng để xây dựng các tập hợp hộp hoạt động một cách tham lam. Chúng ta bắt đầu với 0 hộp và tiếp tục thêm các hộp mới có kích thước \(\lfloor \text{"tổng hiện tại"} / k \rfloor + 1\). Ví dụ, đầu tiên chúng ta sẽ thêm \(k\) hộp kích thước 1 (điều này rõ ràng là cần thiết), sau đó là một hộp kích thước 2, v.v.

Được rồi, bây giờ làm thế nào để chứng minh rằng đây là cách tốt nhất chúng ta có thể làm? Giả sử chúng ta đã đặt một tập hợp \(S\) các hộp hoạt động được. Sắp xếp các hộp từ nhỏ đến lớn và xem xét hộp đầu tiên lớn hơn hộp mà "Thuật toán" sẽ chọn dựa trên tất cả các hộp nhỏ hơn nó. Nói cách khác, nếu hộp này có kích thước \(Y\) và \(N\) là tổng của tất cả các hộp nhỏ hơn nó, thì \(Y > X = \lfloor N/k \rfloor + 1\). (Lưu ý rằng \(X \le C\) vì \(N < k \times C\).) Điều gì xảy ra nếu tất cả các khách hàng đều đặt hàng \(X\) xu? Không có hộp nào có kích thước \(Y\) hoặc lớn hơn có thể được sử dụng, và tổng cộng là \(k \times X > N\), vì vậy tất cả các hộp nhỏ hơn \(Y\) không cộng lại đủ để xử lý chúng. Điều này không thể hoạt động, bất kể chiến lược là gì.

Do đó, mọi hộp trong \(S\), khi được xem xét theo thứ tự, không được lớn hơn hộp mà "Thuật toán" sẽ thêm vào dựa trên các hộp trước đó. Nhưng nếu bất kỳ hộp nào được chọn nhỏ hơn NGHIÊM NGẶT, thì các lựa chọn sau đó của "Thuật toán" đều sẽ bị giảm đi tương ứng (nó có tính đơn điệu theo nghĩa đó). Vì \(S\) phải có tổng ít nhất là \(k \times C\), nếu chúng ta bỏ qua \(S\) và thay vào đó đặt một số lượng hộp tương đương bằng "Thuật toán", tổng của chúng cũng sẽ ít nhất là \(k \times C\). Điều này chứng minh rằng "Thuật toán" là cách tốt nhất chúng ta có thể làm.

Cài đặt

"Thuật toán" thực sự rất, rất đơn giản để lập trình. Trên thực tế, đây là một bản cài đặt hoàn chỉnh cho bài toán Candy Store:

long long T, k, C, prob = 1;
for (cin >> T; T--;) {
  cin >> k >> C;
  long long sum = 0, num_boxes = 0;
  while (sum < k*C) {
    num_boxes++;
    sum += (sum / k) + 1;
  }
  cout << "Case #" << prob++ << ": " << num_boxes << endl;
}

Những điều thú vị khác

Những bạn tinh ý có thể nhận thấy rằng giải pháp này rất tổng quát và không thay đổi ngay cả khi chúng ta thay đổi bài toán một chút. Ví dụ:

• Ràng buộc \(C\) thực tế là vô dụng. Chúng ta có thể bỏ nó đi và để khách hàng đặt bất kỳ số lượng nào, miễn là TỔNG đơn hàng không quá \(k \times C\).
• Chúng ta không thể làm tốt hơn ngay cả khi được biết trước tất cả các đơn hàng của khách hàng (vào đầu ngày). Giải pháp "trực tuyến" (online) cũng tốt như giải pháp "ngoại tuyến" (offline).
• Chúng ta không thể làm tốt hơn ngay cả khi chúng ta ép buộc tất cả khách hàng phải đặt cùng một số lượng như nhau. Đây thực sự là dạng bài toán được đề xuất ban đầu.

Nguồn

Bản dịch dựa trên phân tích chính thức của Google Code Jam 2010 - World Finals - Candy Store, thuộc kho Google Coding Competitions (Apache-2.0).