14/04/2016 03:54:06 PM
Bài viết sưu tầm
Cải tiến thuật toán cho bài "Đóng gói sản phẩm"
Đóng gói sản phẩm.
Ở đầu ra của một dây chuyền sản xuất trong nhà máy ZXY có một máy xếp tự
động. Sau khi kết thúc việc gia công trên dây chuyền, các sản phẩm sẽ được xếp
vào các hộp có cùng dung lượng M. Sản phẩm rời khỏi dây chuyền được xếp vào
hộp đang mở (khi bắt đầu ca làm việc có một hộp rỗng được mở sẵn) nếu như dung
lượng của hộp còn đủ để chứa sản phẩm. Trong trường hợp ngược lại, máy sẽ tự
động đóng nắp hộp hiện tại, cho xuất xưởng rồi mở một hộp rỗng mới để xếp sản
phẩm vào. Trong một ca làm việc có n sản phẩm đánh số từ 1 đến N theo đúng thứ
tự mà chúng rời khỏi dây chuyền. Sản phẩm thứ i có trọng lượng là Ai, i = 1, 2, …,
N. Ban Giám đốc nhà máy qui định rằng sản phẩm xuất xưởng của mỗi ca làm việc
phải được xếp vào trong không quá K hộp.
Yêu cầu: Hãy giúp người quản đốc của ca làm việc xác định giá trị M nhỏ nhất sao
cho số hộp mà máy tự động cần sử dụng để xếp dãy N sản phẩm xuất xưởng của ca
không vượt quá số K cho trước.
Dữ liệu vào: từ file văn bản ZXY.INP:
• Dòng đầu tiên chứa hai số nguyên N và K, (1≤K≤N≤15000);
• Dòng thứ 2 chứa N số nguyên dương Ai (Ai≤105), i =1, 2, …, N.
Các số trên một dòng cách nhau ít nhất một dấu cách.
Kết quả: file ZXY.OUT một số nguyên duy nhất là dung lượng của hộp.
Ví dụ:
ZXY.INP ZXY.OUT
9 4
1 1 1 3 2 2 1 3 1
*Hướng dẫn:
Gọi Max là trọng lượng lớn nhất trong N hộp, S là tổng trọng lượng N hộp.
Cách 1:
Ta thử lần lượt M (M nhận giá trị từ 1 tới S), sau đó kiểm tra xem có chứa N sản
phẩm vào trong K thùng có dung lượng M ko?
Độ phức tạp là O(N.S).
Cách 2:
Bài toán này hoàn toàn có thể giải quyết được bằng phương pháp tìm kiếm nhị
phân.
Chúng ta sẽ chặt nhị phân trong đoạn từ Max đến S để tìm M (vì M chắc chắn nằm
trong đoạn từ Max đến S) như sau:
d := Max; c := S;
Lặp khi d ≤ c:
- M := (d + c)/2
- Dem = so lượng hộp trọng lượng M có thể chứa được N vật phẩm
- Nếu dem > K nghĩa là M quá nhỏ vì vậy cần tăng kích thước của M bằng
cách chặt nhị phân tìm M trong đoạn từ d = M + 1 đến c
- Ngược lại: M đã thỏa mãn có thể chứa được N vật phẩn, tuy nhiên M có thể
chưa là giá trị nhỏ nhất. Vì vậy lưu lại giá trị kq = M, và tìm M có giá trị nhỏ
hơn bằng cách chặt nhị phân tìm M trong đoạn từ d đến c = M – 1
Độ phức tạp là O(N.LogS).
(nguồn bài: Đề thi HSG QG bảng B – năm 2005).
» Tin mới nhất:
- Làm việc với file trong Python (17/09/2025)
- Thực hành với Python và Network (17/09/2025)
- Tạo một service systemd mới trên Linux (15/09/2025)
- SUMO phần mềm mô phỏng hệ thống giao thông (15/09/2025)
- Vision Transformer (ViT) – Khi Transformer bước vào Thị giác Máy tính (14/09/2025)
» Các tin khác:
- Giải bài toán Cổ bằng phương pháp tìm tiếm nhị phân (14/04/2016)
- Sửa đổi cơ sở dữ liệu (05/04/2016)
- Xóa cơ sở dữ liệu trong SQL Server (05/04/2016)
- Backbone framework (02/04/2016)
- Sử dụng bản mẫu xác định yêu cầu phần mềm (17/03/2016)
- Các loại yêu cầu phần mềm (17/03/2016)
- Giới thiệu semantic ui framework (17/03/2016)
- Giới thiệu về Phaser framewrok (17/03/2016)
- Cấu hình và đăng nhập vào hệ thống OpenStack Autopilot Canonical - Phần 2 (16/03/2016)
- Cài đặt OpenStack Private Cloud với OpenStack Autopilot Canonical - Phần 1 (16/03/2016)
