Cơ bản về Quy hoạch động
+2
Admin
bí mật cuộc sống
6 posters
Trang 1 trong tổng số 1 trang
Cơ bản về Quy hoạch động
Chào các bạn, chúng ta đều biết Quy hoạch động là một chiến lược rất hay trong Tin học. Nó xây dựng bài toán ban đầu từ những bài toán con nhỏ hơn có cùng vấn đề. Chính vì vậy, trong Quy hoạch động, nếu phát hiện ra cấu trúc con như vậy là ta đã tìm được cách giải quyết bài toán.
Một đặc điểm ngoài lề mà chúng ta cần chú ý là Quy hoạch động thường chỉ dùng để giải các bài toán thuộc lớp P (tức là tìm được thuật giải trong thời gian đa thức), còn đối với các bài toán NPC (chưa tìm ra thuật giải đa thức để giải quyết nó một cách hữu hiệu) thì ta cần phải sử dụng các chiến lược tìm kiếm kinh nghiệm trong đó.
Đối với các dạng toán về Quy hoạch động chỉ còn cách chúng ta rèn luyện nhiều qua các bài toán cơ bản, từ đó đúc rút về cách thực hiện chiến lược này như thế nào.
Mình xin giới thiệu với các bạn, một bài viết, khá thú vị, khá căn bản để chúng ta cùng rèn luyện thuật toán này của Thầy Nguyễn Thanh Tùng - giảng viên Trường Đại học Sư phạm Hà Nội (Hiện nay Thầy đang học Tiến sĩ về Công nghệ Phần mềm tại Mỹ )
Download tại: Đây
Hi vọng tài liệu này sẽ giúp ích khi các bạn bước chân sử dụng chiến lược này.
Trong kỳ thi Olympic Tin học sinh viên toàn quốc năm 2009 có câu 1 sử dụng Quy hoạch động. Bài toán khá hay, các bạn download về thử giải xem
Một đặc điểm ngoài lề mà chúng ta cần chú ý là Quy hoạch động thường chỉ dùng để giải các bài toán thuộc lớp P (tức là tìm được thuật giải trong thời gian đa thức), còn đối với các bài toán NPC (chưa tìm ra thuật giải đa thức để giải quyết nó một cách hữu hiệu) thì ta cần phải sử dụng các chiến lược tìm kiếm kinh nghiệm trong đó.
Đối với các dạng toán về Quy hoạch động chỉ còn cách chúng ta rèn luyện nhiều qua các bài toán cơ bản, từ đó đúc rút về cách thực hiện chiến lược này như thế nào.
Mình xin giới thiệu với các bạn, một bài viết, khá thú vị, khá căn bản để chúng ta cùng rèn luyện thuật toán này của Thầy Nguyễn Thanh Tùng - giảng viên Trường Đại học Sư phạm Hà Nội (Hiện nay Thầy đang học Tiến sĩ về Công nghệ Phần mềm tại Mỹ )
Download tại: Đây
Hi vọng tài liệu này sẽ giúp ích khi các bạn bước chân sử dụng chiến lược này.
Trong kỳ thi Olympic Tin học sinh viên toàn quốc năm 2009 có câu 1 sử dụng Quy hoạch động. Bài toán khá hay, các bạn download về thử giải xem
Re: Cơ bản về Quy hoạch động
Mình thấy quy hoạch động là một thuật toán rất hay, dùng để giải hầu hết các bài toán tối ưu. Dạng toán này cũng rất phổ biến trong các kỳ thi olympic tin học, tin học trẻ quốc gia và các giải quốc tế (IOI).
Rất cảm ơn bạn đã share một tài liệu khá hay về quy hoạch động. mình cũng xin chia sẻ một vài tài liệu khác về dạng QHD.
Download
Download
Rất cảm ơn bạn đã share một tài liệu khá hay về quy hoạch động. mình cũng xin chia sẻ một vài tài liệu khác về dạng QHD.
Download
Download
Re: Cơ bản về Quy hoạch động
Chưa đọc nội dung nhưng đây là cái mà m rất cần. Thank
sptinhoc- Thành viên mới
- Ngày sinh : 12/10/1988
Tuổi : 35
Ngày đăng ký : 11/01/2010
quangfieu_s2- Thành viên mới
- Ngày sinh : 28/03/1996
Tuổi : 28
Ngày đăng ký : 11/12/2010
Re: Cơ bản về Quy hoạch động
quangfieu_s2 đã viết:hay
hoang2596- Thành viên mới
- Ngày sinh : 02/05/1996
Tuổi : 27
Ngày đăng ký : 11/12/2010
Re: Cơ bản về Quy hoạch động
co hieu cai deo j dau ma keu hayquangfieu_s2 đã viết:hay
Cảnh cáo : hoang2596
Lý do : sử dụng từ ngữ thô tục.
hoang2596- Thành viên mới
- Ngày sinh : 02/05/1996
Tuổi : 27
Ngày đăng ký : 11/12/2010
Re: Cơ bản về Quy hoạch động
Bài 1 trong đề thi khối chuyên tin Olympic sinh viên này khá hay: Đề ở Đây
Ý tưởng: Sử dụng Quy hoạch động
Gọi max1 là giá trị lớn nhất của ak trong các sốtừ (a1, a2,…, ai)
Gọi max2 là giá trị lớn nhất của ak1 + 2ak2(k1 < k2) trong các số từ (a1, a2,…, ai)
Gọi max3 là giá trị lớn nhất của ak1 + 2ak2+ 3ak3 (k1 < k2 < k3) trong các số từ (a1, a2,…, ai).
Như vậy: Với 3 số a1, a2, a3thì:
max3 = a1+ 2a2 + 3a3
max2 = max(a1 + 2a2, a2+ 2a3, a1 + 2a3)
max1 = max(a1, a2, a3)
Ta sử dụng Quy hoạch động:
for i:= 4 to n do
begin
max3 = max(max3,max2 + 3ai);
max2 = max(max2,max1 + 2ai);
max1 = max(max1,ai);
end;
Ý tưởng: Sử dụng Quy hoạch động
Gọi max1 là giá trị lớn nhất của ak trong các sốtừ (a1, a2,…, ai)
Gọi max2 là giá trị lớn nhất của ak1 + 2ak2(k1 < k2) trong các số từ (a1, a2,…, ai)
Gọi max3 là giá trị lớn nhất của ak1 + 2ak2+ 3ak3 (k1 < k2 < k3) trong các số từ (a1, a2,…, ai).
Như vậy: Với 3 số a1, a2, a3thì:
max3 = a1+ 2a2 + 3a3
max2 = max(a1 + 2a2, a2+ 2a3, a1 + 2a3)
max1 = max(a1, a2, a3)
Ta sử dụng Quy hoạch động:
for i:= 4 to n do
begin
max3 = max(max3,max2 + 3ai);
max2 = max(max2,max1 + 2ai);
max1 = max(max1,ai);
end;
Re: Cơ bản về Quy hoạch động
ax ax. phe^ wa'
Cảnh báo : post bài không đúng chủ đề
Cảnh báo : post bài không đúng chủ đề
tranhoangnam- Thành viên mới
- Ngày sinh : 27/11/1996
Tuổi : 27
Đến từ : hai phong
Ngày đăng ký : 01/01/2011
Trang 1 trong tổng số 1 trang
Permissions in this forum:
Bạn không có quyền trả lời bài viết
|
|
15/4/2011, 10:34 pm by funny
» Mọi người làm giúp tôi bài này với !
13/4/2011, 11:42 am by phonggia
» Giúp mình giải bài này với
12/4/2011, 1:00 pm by ldt
» Chia se 1 bai paccal ve ve do thi
11/4/2011, 1:55 pm by duy_sau_rom
» đồ hoạ trong pascal
9/4/2011, 9:16 pm by jetlongk4
» Giá trị biểu thức bằng kí pháp nghịch đảo
1/4/2011, 8:49 am by kh1132000
» AI GIẢI GIÚP EM BÀI NÀY VỚi , ĐANG CẦN GẤP GẤP LẮM :(
31/3/2011, 11:47 pm by jancancook
» dòng thời gian
31/3/2011, 11:31 am by gianggiangonline
» anh nào giúp em với
30/3/2011, 11:00 pm by sieuhoatinh
» VTC trả lương 10 triệu cho SV tốt nghiệp ĐH Văn Hiến - khoa CNTT - ĐTVT tại Hà Nội
29/3/2011, 2:48 pm by SV_tuonglai
» Download cẩm nang mùa thi 2011 tại đây
29/3/2011, 2:47 pm by SV_tuonglai
» Check giúp mình lỗi trong code này với !
27/3/2011, 10:07 pm by mamap0511
» Tai nghe sony dr 370 ve hang moi
25/3/2011, 8:42 pm by hs_bin
» giúp em với
25/3/2011, 12:11 pm by nbni
» Headphone sony dr 370 moi ve hang
24/3/2011, 9:13 pm by hs_bin
» GIUP EM MAY BAI PASCAL CO BAN ( EM MOI HOC PASCAL)
24/3/2011, 9:11 pm by tuan045610
» Headphone sony DR 370 moi ve hang
21/3/2011, 8:11 pm by hs_bin
» Sony DR 310 moi ve hang
20/3/2011, 9:34 pm by hs_bin
» Mọi người giúp dùm em!!^^
20/3/2011, 9:53 am by trangbui_thcstanhiep
» bài tập về hàm trog pascal
18/3/2011, 10:34 pm by sieuhoatinh