背包問題九講_doc版

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

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

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

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

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