




版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、動(dòng)態(tài)規(guī)劃2、單擊添加文本,單擊添加文本,單擊添加文本,解釋經(jīng)典示例,示例1包裝問(wèn)題(noi openjudge 8785)問(wèn)題描述:有一個(gè)容量為V(正整數(shù),0=v=20000)的箱子,并且有N個(gè)物品(0 n=30),每個(gè)物品都有。要求將任意數(shù)量的N個(gè)物品包裝到箱子中,以最小化箱子的剩余空間。輸入第一行是整數(shù)v,表示盒子的容量。第二行是整數(shù)n,表示項(xiàng)目數(shù)。以下n行,每一行都有一個(gè)正整數(shù)(不超過(guò)10000),分別代表這n個(gè)項(xiàng)目各自的體積。輸出一個(gè)整數(shù),表示盒子的剩余空間。單擊添加文本,單擊添加文本,單擊添加文本,單擊添加文本,解釋經(jīng)典示例,示例輸入24 6 8 3 12 7 9 7示例輸出0。單擊
2、添加文本,單擊添加文本,單擊添加文本,單擊添加文本,解釋經(jīng)典示例,問(wèn)題分析狀態(tài):fi,j表示裝在j個(gè)重包中的第一個(gè)I個(gè)對(duì)象的最優(yōu)解方程:fi,j=max(fi-1,j,fi-1,j-ai);點(diǎn)擊添加文本,點(diǎn)擊添加文本,點(diǎn)擊添加文本,點(diǎn)擊添加文本,程序?qū)崿F(xiàn),點(diǎn)擊添加文本,點(diǎn)擊添加文本,點(diǎn)擊添加文本,解釋經(jīng)典示例,示例2 usaco問(wèn)題描述:貝西在珠寶店閑逛時(shí)買(mǎi)了一個(gè)心愛(ài)的手鐲。自然,她想從她收集的N(1=N=3,402)顆寶石中挑選出最好的,并將它們鑲嵌在手鐲上。至于第二顆寶石,它的重量是W_i(1=W_i=400),貝西知道它的魅力值D_i(1=D_i=100),它可以在鑲嵌手鐲后增加自己的魅
3、力。由于貝西只能忍受重量不超過(guò)1米(1=12,880米)的手鐲,她可能無(wú)法鑲嵌所有她喜歡的寶石。所以貝西來(lái)找你,告訴你她所有寶石的屬性和她能承受的重量。我希望你能幫她計(jì)算一下,如果按照最合理的方案鑲嵌寶石,她的魅力值還能增加多少。單擊添加文本,單擊添加文本,單擊添加文本,單擊添加文本,并解釋經(jīng)典示例。輸入格式的第一行有兩個(gè)整數(shù)N(1=N=3,402)和M(1=M=12,880),接下來(lái)的N行每行有兩個(gè)整數(shù)分別代表寶石的重量和魅力值。輸出格式輸出只包含一行,其中只包含一個(gè)整數(shù),表示魅力值最多可以增加多少。示例輸入 3 70 71 100 69 1 1 2示例輸出3,單擊添加文本,單擊添加文本,單
4、擊添加文本,解釋經(jīng)典示例,問(wèn)題分析狀態(tài):fi,j代表佩戴j重手上的第一個(gè)I寶石獲得的最大魅力值:fi,j=max (fi-1,j單擊添加文本,單擊添加文本,單擊添加文本,單擊添加文本,單擊添加文本,程序?qū)崿F(xiàn),單擊添加文本,單擊添加文本,單擊添加文本,單擊添加文本,單擊添加文本,單擊添加文本,解釋經(jīng)典示例, 例3奶牛工作問(wèn)題描述:奶牛Bassie去DQ工作,遇到一位顧客,他給了一大筆錢(qián),所以Bassie不得不面對(duì),以便給顧客零錢(qián)。因?yàn)槟膛5氖种赣邢?,他只能向你求助?(眾所周知,零的總數(shù)是總數(shù))(1=總數(shù)=1000,1=N=1000,1=人工智能=300)有多少個(gè)解?單擊添加文本,單擊添加文本,
5、單擊添加文本,單擊添加文本,解釋經(jīng)典示例,輸入格式的第一行是硬幣總值和硬幣類(lèi)型數(shù)n以下n行是數(shù)值ai,i=1,2,3.n輸出格式行,解的數(shù)目樣本輸入83 5 50 25 10 5 1樣本輸出 159。單擊添加文本,單擊添加文本,單擊添加文本,單擊添加文本,并解釋經(jīng)典示例。0 x 50 0 x 25 0 x 10 0 x 5 83 x 1 0 x 50 0 x 25 0 x 10 1 x 5 78 x 1 0 x 50 0 x 25 0 x 10 2 x 5 73 x 1 0 x 50 0 x 25 0 x 10 3 x 5 68 x 1 0 x 50 0 x 25 0 x 10 4 x 5 6
6、3 x 1 0 x 50 x 25 0 x 10 5 x 5 58 x 1 0 x 50 0 x 25 0 x 10 6 x 5 53 x 1 0 x 50 0 x 25 0 x 10 7 x 5 48 x 1 0 x 50 0 x 25 0 x 10 8 x 5 43 x 1 0 x 50 0 x 25 0 x 10 9 x 5 38 x 1 0 x 50 x 25 0 x 10 x 5 33 X 1 0 X 50 0 X 25 0 X 10 11 X 5 28 X 1 0 X 50 0 X 25 0 X 10 12 X 5 23 X 1 0 X 50 0 X 25 0 X 10 13 X
7、5 18 X 1 0 X 50 X 25 0 X 10 14 X 5 13 X 1,示例說(shuō)明,單擊添加文本,單擊添加文本,單擊添加文本,解釋經(jīng)典示例, 問(wèn)題分析狀態(tài):fi表示面值為I: fi=sum (fi-AK) 1的貨幣兌換方案的數(shù)量,單擊添加文本,單擊添加文本,單擊添加文本,單擊添加文本,程序?qū)崿F(xiàn),單擊添加文本,單擊添加文本,單擊添加文本,解釋經(jīng)典示例,示例4滑雪問(wèn)題描述:邁克爾喜歡滑雪。 這并不奇怪,因?yàn)榛┱娴暮艽碳?。然而,為了獲得速度,滑行區(qū)域必須向下傾斜,當(dāng)你滑到斜坡底部時(shí),你必須再次上坡或等待電梯來(lái)接你。邁克爾想知道一個(gè)地區(qū)最長(zhǎng)的滑坡。該區(qū)域由二維數(shù)組給出。數(shù)組中的每個(gè)數(shù)字代表
8、一個(gè)點(diǎn)的高度。單擊添加文本,單擊添加文本,單擊添加文本,單擊添加文本,解釋經(jīng)典示例,這里有一個(gè)示例1 2 3 4 5 16 17 19 6 15 25 20 7 14 23 21 8 13 12 11 10 9一個(gè)人不能從某個(gè)點(diǎn)滑動(dòng)到上下左右四個(gè)相鄰點(diǎn)中的一個(gè),如果且僅當(dāng)高度降低,在上面的示例中,一個(gè)可行的人不能滑動(dòng)如下。當(dāng)然,252423321更長(zhǎng)。事實(shí)上,這是最長(zhǎng)的一個(gè)。輸入格式第一行表示區(qū)域的二維陣列的行數(shù)r和列數(shù)C(1R,C100)。下面是R行,每行有代表高度的C數(shù)。輸出格式該區(qū)域中最長(zhǎng)滑坡的長(zhǎng)度,單擊添加文本,單擊添加文本,單擊添加文本,解釋經(jīng)典示例,示例輸入5 5 123 4 5
9、16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9示例輸出 25,單擊添加文本,單擊添加文本,單擊添加文本,單擊添加文本,解釋經(jīng)典示例,問(wèn)題分析類(lèi)似的最長(zhǎng)下降序列,并列舉每個(gè)最低點(diǎn)。通過(guò)記憶搜索來(lái)寫(xiě)作更方便。單擊添加文本,單擊添加文本,單擊添加文本,單擊添加文本,程序?qū)崿F(xiàn),單擊添加文本,單擊添加文本,單擊添加文本,解釋經(jīng)典示例,示例5最小成本母樹(shù)的問(wèn)題描述:有n堆沙子排成一行,每堆沙子有一個(gè)數(shù)量,例如:13 7 8 16 21 4 18。任何兩個(gè)相鄰的沙堆都可以合并。當(dāng)兩堆沙子合并成一堆時(shí),兩堆沙子的總和被稱(chēng)為合并兩堆沙子的成本。經(jīng)過(guò)連續(xù)的合并,這些沙子最終被組合成一堆,所有合并成本的總和稱(chēng)為總成本。例如,在上表中,兩個(gè)合并方案的成本為:第一個(gè)方案的總成本為20.24.25.44.69.87=267,第二個(gè)方案的總成本為15.37.22.28.59.87=248。因此,不同合并過(guò)程的總成本是不同的。問(wèn)題:當(dāng)給定n的個(gè)數(shù)時(shí),找到一個(gè)合理的合并方法來(lái)最小化總成本。,單擊添加文本,單擊添加文本,單擊添加文本,單擊添加文本,解釋經(jīng)典示例和問(wèn)題分析狀態(tài):fi,j表示
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025至2030中國(guó)男茄克行業(yè)發(fā)展分析及競(jìng)爭(zhēng)格局與發(fā)展趨勢(shì)預(yù)測(cè)報(bào)告
- 2025至2030中國(guó)電子出版物行業(yè)深度研究及發(fā)展前景投資評(píng)估分析
- 2025至2030中國(guó)甲硝唑片行業(yè)產(chǎn)業(yè)運(yùn)行態(tài)勢(shì)及投資規(guī)劃深度研究報(bào)告
- 《醫(yī)療機(jī)構(gòu)工作人員廉潔從業(yè)九項(xiàng)準(zhǔn)則》考核試卷(含答案)
- 茶藝知識(shí)培訓(xùn)課件
- 農(nóng)林高校研究生課程思政建設(shè)評(píng)價(jià)研究
- 技術(shù)助力下的翻轉(zhuǎn)課堂教學(xué)相長(zhǎng)的實(shí)踐案例
- 郵電系統(tǒng)培訓(xùn)課件資源
- 2025年中國(guó)PU球場(chǎng)數(shù)據(jù)監(jiān)測(cè)研究報(bào)告
- 構(gòu)建數(shù)字化教育公平的橋梁設(shè)計(jì)思維的智慧
- 《微生物污水處理》課件
- SEO與用戶體驗(yàn)設(shè)計(jì)在醫(yī)療安全產(chǎn)品中的應(yīng)用
- DB51T 2628-2019 司法所外觀及室內(nèi)標(biāo)識(shí)規(guī)范
- 廣西大學(xué)《電機(jī)學(xué)》期末復(fù)習(xí)題及參考答案
- 2024年度破碎機(jī)生產(chǎn)原料供應(yīng)與采購(gòu)合同
- 外賣(mài)配送人員勞動(dòng)合同
- 《義務(wù)教育數(shù)學(xué)課程標(biāo)準(zhǔn)(2022年版)》初中內(nèi)容解讀
- 精神疾病患者的麻醉管理
- 高一物理競(jìng)賽試題及答案
- 醫(yī)院預(yù)約平臺(tái)建設(shè)方案
- 生命體征課件教學(xué)課件
評(píng)論
0/150
提交評(píng)論