//
you're reading...
Bài tập huấn luyện, Chủ đề quy hoạch động, Đề ôn luyện thi học kỳ

Bài tập huấn luyện: Cây xăng

Bài 165/2003 (THNT) – Tìm vị trí


Đề bài


Một đại lý kinh doanh xăng dầu có n trạm bán xăng dầu (gọi tắt là cây xăng) đánh số từ 1 đến n trên một đường cao tốc muốn tìm vị trí đặt k bể chứa xăng để cung ứng xăng cho các cây xăng. Trên đường cao tốc người ta đặt các cột mốc cây số, bắt đầu từ cột số 0. Biết vị trí của cây xăng thứ i là ở cột cây số di (i=1,2,…,n): d1 < d2 < …n.

Yêu cầu:

Tìm vị trí đặt k bể chứa xăng tại k trong số n cây xăng sao cho khoảng cách lớn nhất từ cây xăng không có bể chứa đến cây xăng có bể chứa gần nó nhất là nhỏ nhất.

Dữ liệu:

Vào từ file văn bản VITRI.INP

– Dòng đầu tiên ghi 2 số nguyên dương n, k (n<200, k<30, k<n).
– Dòng thứ 2 ghi các số d1, d2,…,dn (di là các số nguyên dương không quá 320000). Các số trên cùng một dòng ghi cách nhau ít nhất một dấu trắng.

Kết quả:

Ghi ra file văn bản VITRI.OUT
File gồm k dòng, mỗi dòng ghi chỉ số cây xăng đặt bể chứa xăng.

Ví dụ:

VITRI.INP VITRI.OUT
6   3

5   6   12   19   20   27

2

4

6


Hướng dẫn


Tư tưởng thuật toán:
Đây là một bài toán tối ưu, nên phương pháp tốt nhất mà chúng ta chọn để giải quyết là Quy Hoạch Động. Gọi S[i,j] là khoảng cách nhỏ nhất cần tìm khi đã bố trí được i bể xăng, trong
đó bể xăng thứ i được bố trí ở cây xăng j. Dễ thấy s[1,j] = d[j]-d[1], và s[i,i] = 0 (vì i bể xăng được bố trí ở i cây xăng liên tiếp lên). Ta sẽ tìm cách bố trí lần lượt từng bể xăng một.

Nhận thấy bể xăng i có thể được bố trí từ cây xăng i đến cây xăng n – (k-i).

Công thức quy hoạch động: s[i,j]:= Max(s[i-1,h],ff(h,j)); trong đó: h là vị trí có thể bố trí được của bể xăng i -1 khi bố trí bể xăng i tại vị trí j, như vậy h: i-1 … j-1. Còn ff(h,j) là khoảng cách lớn nhất của các cây xăng tới bể xăng gần nó nhất (các cây xăng này nằm giữa bể xăng i-1 và i, nói cách khác là các cây xăng này nằm giũa cây xăng h và cây xăng j). Việc tính ff(h,j) rất đơn giản (tham khảo chương trình mẫu). Sau khi xây dựng được bảng s, ta sẽ tìm ngược lại vị trí đặt các bể xăng, để làm được điều này ta cần có mảng Vtr[i,j]: bể xăng i-1 đặt tại vị trí cây
xăng vtr[i,j].


Chương trình


[Xem chương trình]

About pascalteacher

Trang thông tin Toán học và Tin học

Thảo luận

Chưa có phản hồi.

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

Các tác giả

Tháng Mười Hai 2016
M T W T F S S
« Nov    
 1234
567891011
12131415161718
19202122232425
262728293031  

NCT Computer

Flickr Photos

A bellezza di a natura (C☺rsica)

Southern White-faced Owl D75_5752.jpg

2016 Lake Yamanaka winter Fuji

More Photos

Thống kê

  • 78,768 lượt xem

%d bloggers like this: