動(dòng)規(guī)-背包九講完整版

1、背包問(wèn)題九講背包問(wèn)題九講v1.0v1.0目錄第一講01背包問(wèn)題第二講完全背包問(wèn)題第三講多重背包問(wèn)題第四講混合三種背包問(wèn)題第五講二維費(fèi)用的背包問(wèn)題第六講分組的背包問(wèn)題第七講有依賴的背包問(wèn)題第八講泛化物品第九講背包問(wèn)題問(wèn)法的變化附：USACO中的背包問(wèn)題前言前言本篇文章是我(dd_engi)正在進(jìn)行中的一個(gè)雄心勃勃的寫作計(jì)劃的一部分，這個(gè)計(jì)劃的內(nèi)容是寫作一份較為完善的NOIP難度的動(dòng)態(tài)規(guī)劃總結(jié)，名為《解動(dòng)態(tài)規(guī)劃題的基本思考方式》。現(xiàn)在你看到

2、的是這個(gè)寫作計(jì)劃最先發(fā)布的一部分。背包問(wèn)題是一個(gè)經(jīng)典的動(dòng)態(tài)規(guī)劃模型。它既簡(jiǎn)單形象容易理解，又在某種程度上能夠揭示動(dòng)態(tài)規(guī)劃的本質(zhì)，故不少教材都把它作為動(dòng)態(tài)規(guī)劃部分的第一道例題，我也將它放在我的寫作計(jì)劃的第一部分。讀本文最重要的是思考。因?yàn)槲业恼Z(yǔ)言和寫作方式向來(lái)不以易于理解為長(zhǎng)，思路也偶有跳躍的地方，后面更有需要大量思考才能理解的比較抽象的內(nèi)容。更重要的是：不大量思考，絕對(duì)不可能學(xué)好動(dòng)態(tài)規(guī)劃這一信息學(xué)奧賽中最精致的部分。你現(xiàn)在看到的是本文的

3、1.0正式版。我會(huì)長(zhǎng)期維護(hù)這份文本，把大家的意見(jiàn)和建議融入其中，也會(huì)不斷加入我在OI學(xué)習(xí)以及將來(lái)可能的ACMICPC的征程中得到的新的心得。但目前本文還沒(méi)有一個(gè)固定的發(fā)布頁(yè)面，想了解本文是否有更新版本發(fā)布，可以在OIBH論壇中以“背包問(wèn)題九講”為關(guān)鍵字搜索貼子，每次比較重大的版本更新都會(huì)在這里發(fā)貼公布。目錄目錄第一講第一講0101背包問(wèn)題這是最基本的背包問(wèn)題，每個(gè)物品最多只能放一次。第二講第二講完全背包問(wèn)題完全背包問(wèn)題?donglixp

4、他們每人都最先指出了本文第一個(gè)beta版中的某個(gè)并非無(wú)關(guān)緊要的錯(cuò)誤。謝謝你們?nèi)绱俗屑?xì)地閱讀拙作并彌補(bǔ)我的疏漏。感謝XiaQ，它針對(duì)本文的第一個(gè)beta版發(fā)表了用詞嚴(yán)厲的六條建議，雖然我只認(rèn)同并采納了其中的兩條。在所有讀者幾乎一邊倒的贊揚(yáng)將我包圍的當(dāng)時(shí)，你的貼子是我的一劑清醒劑，讓我能清醒起來(lái)并用更嚴(yán)厲的眼光審視自己的作品。當(dāng)然，還有用各種方式對(duì)我表示鼓勵(lì)和支持的幾乎無(wú)法計(jì)數(shù)的同學(xué)。不管是當(dāng)面贊揚(yáng)，或是在論壇上回復(fù)我的貼子，不管是發(fā)來(lái)熱情

5、洋溢的郵件，或是在即時(shí)聊天的窗口里豎起大拇指，你們的鼓勵(lì)和支持是支撐我的寫作計(jì)劃的強(qiáng)大動(dòng)力，也鞭策著我不斷提高自身水平，謝謝你們！最后，感謝Emacs這一世界最強(qiáng)大的編輯器的所有貢獻(xiàn)者，感謝它的插件EmacsMuse的開(kāi)發(fā)者們，本文的所有編輯工作都借助這兩個(gè)卓越的自由軟件完成。謝謝你們——自由軟件社群——為社會(huì)提供了如此有生產(chǎn)力的工具。我深深欽佩你們身上體現(xiàn)出的自由軟件的精神，沒(méi)有你們的感召，我不能完成本文。在你們的影響下，采用自由文檔