//
you're reading...
00 - Chủ đề chung, Bài tập huấn luyện, Chủ đề quy hoạch động

Chuyên đề quy hoạch động: Con kiến


Đề bài


conkien
Trên một sân hình chữ nhật MxN, được chia thành các ô vuông đơn vị, mỗi ô chứa một lượng thức ăn. Một con kiến xuất phát từ ô (1,1) muốn đi qua sân để đến dòng thứ M. Con kiến chỉ có thể đi theo một dòng chia nhỏ trên sân ứng với một dòng của bảng chữ nhật hoặc đi theo trên một cột của sân. Hãy chỉ ra đường đi giúp con kiến có được nhiều thức ăn nhất.

FOOD.INP
3 5

7   3   8   1    5

8   8   3   14   1

6  15  19   1    1


Hướng dẫn


Công thức quy hoạch
B[i,j] là lượng thức ăn lớn nhất đi từ ô (1,1) đến ô (i,j)
B[1,j] = A[1,j] với j = 1..N
B[i,1] = A[i,1]+B[i-1,1] với i = 2..M
B[i,j] =Max{B[i-1,j],B[i,j-1]} + A[i,j] với i = 2..M và j = 2..N


Chương trình


[Xem]

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 Một 2016
M T W T F S S
« Oct   Dec »
 123456
78910111213
14151617181920
21222324252627
282930  

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: