Bài tập lớn: Sử dụng phương pháp qui hoạch động giải bài toán cái túi

Bài tập lớn "Sử dụng phương pháp qui hoạch động giải bài toán cái túi" để giải bài toán cái túi, chúng ta cần dùng phương pháp nào để đạt hiệu quả cao nhất, sử dụng phương pháp quy hoạch động làm tăng hiệu suất trong các thao tác xử lý. Mời các bạn cùng tham khảo!
Nội dung trích xuất từ tài liệu:
Bài tập lớn: Sử dụng phương pháp qui hoạch động giải bài toán cái túi TRƯỜNGĐẠIHỌCHỒNGĐỨC KHOA:CNTT&TT BÀITẬPLỚN MÔN:PHÂNTÍCHVÀTHIẾTKẾTHUẬTTOÁN ĐỀTÀI:“SỬDỤNGPHƯƠNGPHÁPQUIHOẠCHĐỘNGGIẢI BÀITOÁNCÁITÚI”Họvàtên:ĐỗViếtVũMãSốViên:1561030049 Lớp:K18–ĐHCNTT GiáoviênHD:TrịnhThịPhú 1 ThanhHóa,tháng4,năm2017 MỤCLỤC LờimởđầuCùngvớisựpháttriểncủakhoahọckĩthuật,côngnghệthôngtinnóichungvà bộmônphântíchvàthiếtkếthuậttoánnóiriêngngàycàngđượcứngdụngrộngrãitrongnhiềulĩnhvực.Vớimộtcơ sở dữ liệukhổnglồ,việc đưara mộtphươngphápnhằmgiảiquyếtvấnđề tìmkiếmdữ liệucóhiệuquả vànhanhchóngnhấtluônđượcsự quantâmcủacácnhàpháttriểnphầnmềm.Thông thườngcórấtnhiềuphươngphápđểgiảiquyếtmộtbàitoán.Việctruysuấtdữliệuchưađạthiệuquả cao.Sửdụngphươngphápquyhoạchđộnglàmộtgiải pháplàmtănghiệusuấttrongcácthaotácxửlý.Vấnđề đặtra:đểgiảibàitoáncáitúi,chúngtacầndùngphươngphápnào để đạthiệuquả caonhất.Để giảiquyếtvấnđề trêntacùngtìmhiểuphươngphápquyhoạchđộng.I. CƠSỞLÝTHUYẾT 1. Kháiniệm Quyhoạchđộnglàmộtphươngphápgiảmthờigianchạycủacácthuật toánthểhiệncáctínhchấtcủacácbàitoáncongốinhau(overlapping subproblem)vàcấutrúccontốiưu(optimalsubstructure). 2. Cáchti ếpcận - Topdown(Từ trênxuống):Bàitoánđượcchiathànhcácbàitoáncon,các bàitoánconnàyđượcgiảivàlờigiảiđượcghinhớ để phòngtrườnghợp cầndùnglạichúng.Đâylàđệquyvàlưutrữđượckếthợpvớinhau. - Bottomup(Từdướilên):Tấtcảcácbàitoánconcóthểcầnđếnđềuđược giảitrước,sauđóđượcdùngđểxâydựnglờigiảichocácbàitoánlớnhơn. Cáchtiếpcậnnàyhơitốthơnvềkhônggianbộnhớdùngchongănxếpvà sốlờigọihàm.Tuynhiên,đôikhiviệcxácđịnhtấtcảcácbàitoánconcần thiếtchoviệcgiảiquyếtbàitoánchotrướckhôngđượctrựcgiáclắm. 3. Cácbướcgiảim ộtbàitoánvớicấutrúccontốiưu - Chiabàitoánthànhcácbàitoánconnhỏhơn. - Giảicácbàitoánnàymộtcáchtốiưubằngcáchsửdụngđệquy. - Sửdụngcáckếtquảtốiưuxâydựngmộtlờigiảitốiưuchobàitoánban đầu. 4. Cácbướcgiảimộtbàitoánquyhoạchđộng - Tênvàýnghĩacácbiếnphụcvụsơđồlặp. - Cáchkhaibáocácbiếnđó. - Sơđồ(côngthức)lặpchuyểntừmộtbướcsangbướctiếptheo. 3 - Giátrịđầucủacácbiếnthamgiatínhlặp. - Thamsốđiềukhiểnlặp:thayđổitừđâuđếnđâu. - Kếtquả:ởđâuvàlàmthếnàođểdẫnxuấtra.II. BÀITOÁNCÁITÚI1. MôhìnhbàitoánBàitoánxếpcáitúi(haylàbàitoánbalô)làmộtbàitoántốiưuhóatổhợp.Bàitoánđượcđặttêntừ vấnđề chọnnhữnggìquantrọngcóthể bỏvừavàotrongmộtcáitúi(vớigiớihạnkhốilượng)đểmangtheotrongmột chuyếnđi.Cácbàitoántươngtựthườngxuấthiệntrongkinhdoanh,toántổhợp,lýthuyếtđộphứctạptínhtoán,mậtmãhọcvàtoánứngdụng.2. Xâydựnghướnggiải a. Nhậpvàxuấtdữliệu - Chọnphươngánkhaibáobiếntoàncục. - Chọncáchnhậpdữliệutừbànphímvàxuấtbảngtínhramànhình. b. Xâydụngbảngtínhbằngphươngphápquihoạchđộng - Hàmmụctiêuf:tổnggiátrịcủacáitúi(vali). - Nhậnxét:giátrị củacáitúiphụ thuộcvàohaiyếutố,đólàgiátrị củacái túivàtrọnglượngcủacácđồvật.Dođótacóthểdùngmảnghaichiềuđể lưutrữ.F[i][j]:làtổnggiátrị lớnnhấtcủacáitúikhixéttừ vậtthứ 1đến vậtthứivàtrọnglượngkhôngvượtquáj. - Khixétđếnf[i][j]thìcácgiátrịtrênbảngphươngánđềuđượtốiưu. - Tínhf[i][j]có3khảnăngxảyra: Nếuf[i][0]=0vàf[0][j]=0. Nếua[i]>jthìf[i][j]=f[i1][j]. Nếua[i] printf( Nhapvaosocongdungcuadovatthu%d=,i); scanf(%d,&c[i]); }}//xuatbangtinhvoidxua ...