#title 背包問題九講    version 1.1 build 20071115<contents>* 前言本篇文章是我(dd_engi)正在進行中的一個雄心勃勃的寫作計劃的一部分，這個計劃的內(nèi)容是寫作一份較為完善的NOIP難度的動態(tài)規(guī)劃總結(jié)，名為《解動態(tài)規(guī)劃題的基本思考方式》。現(xiàn)在你看到的是這個寫作計劃最先發(fā)布的一部分。背包問題是一個經(jīng)典的動態(tài)規(guī)劃模型。它既簡單形象容易理解，又在某種程度上能夠揭示動態(tài)規(guī)劃的本質(zhì)，故不少教材都把它作為動態(tài)規(guī)劃部分的第一道例題，我也將它放在我的寫作計劃的第一部分。讀本文最重要的是思考。因為我的語言和寫作方式向來不以易于理解為長，思路也偶有跳躍的地方，后面更有需要大量思考才能理解的比較抽象的內(nèi)容。更重要的是：不大量思考，絕對不可能學(xué)好動態(tài)規(guī)劃這一信息學(xué)奧賽中最精致的部分。你現(xiàn)在看到的是本文的v1.1版，發(fā)布于2007年11月15日。我會長期維護這份文本，把大家的意見和建議融入其中，也會不斷加入我在OI學(xué)習(xí)以及將來可能的ACM-ICPC的征程中得到的新的心得。但目前本文還沒有一個固定的發(fā)布頁面，想了解本文是否有更新版本發(fā)布，可以在[[http://oibh.org/bbs/][OIBH論壇]]中以“背包問題九講”為關(guān)鍵字搜索貼子，每次比較重大的版本更新都會在這個論壇里發(fā)貼公布。也可以用“背包問題九講”為關(guān)鍵字在搜索引擎中搜索以得到最新版本。* 目錄** [[P01][第一講 01背包問題]]這是最基本的背包問題，每個物品最多只能放一次。** [[P02][第二講 完全背包問題]]第二個基本的背包問題模型，每種物品可以放無限多次。** [[P03][第三講 多重背包問題]]每種物品有一個固定的次數(shù)上限。** [[P04][第四講 混合三種背包問題]]將前面三種簡單的問題疊加成較復(fù)雜的問題。** [[P05][第五講 二維費用的背包問題]]一個簡單的常見擴展。** [[P06][第六講 分組的背包問題]]一種題目類型，也是一個有用的模型。后兩節(jié)的基礎(chǔ)。** [[P07][第七講 有依賴的背包問題]]另一種給物品的選取加上限制的方法。** [[P08][第八講 泛化物品]]我自己關(guān)于背包問題的思考成果，有一點抽象。** [[P09][第九講 背包問題問法的變化]]試圖觸類旁通、舉一反三。** [[P10][附錄一：USACO中的背包問題]]給出 USACO Training 上可供練習(xí)的背包問題列表，及簡單的解答。** [[P11][附錄二：背包問題的搜索解法]]除動態(tài)規(guī)劃外另一種背包問題的解法。* 聯(lián)系方式如果有任何意見和建議，特別是文章的錯誤和不足，或者希望為文章添加新的材料，可以通過[[http://kontactr.com/user/tianyi/]]這個網(wǎng)頁聯(lián)系我。值得說明的是，如果有OI方面的問題，例如不明白自己的程序為什么錯了或者索要某種算法的源代碼，使用這個聯(lián)系方式可能得不到及時解答。請在[[http://oibh.org/bbs/][OIBH論壇]]發(fā)問。* 致謝感謝以下名單： - 阿坦 - jason911 - donglixp - LeafDuo他們每人都最先指出了本文曾經(jīng)存在的某個并非無關(guān)緊要的錯誤。謝謝你們?nèi)绱俗屑?xì)地閱讀拙作并彌補我的疏漏。感謝 XiaQ，它針對本文的第一個beta版發(fā)表了用詞嚴(yán)厲的六條建議，雖然我只認(rèn)同并采納了其中的兩條。在所有讀者幾乎一邊倒的贊揚將我包圍的當(dāng)時，你的貼子是我的一劑清醒劑，讓我能清醒起來并用更嚴(yán)厲的眼光審視自己的作品。sfita 提供了[[P01]]中的“一個常數(shù)優(yōu)化”。當(dāng)然，還有用各種方式對我表示鼓勵和支持的幾乎無法計數(shù)的同學(xué)。不管是當(dāng)面贊揚，或是在論壇上回復(fù)我的貼子，不管是發(fā)來熱情洋溢的郵件，或是在即時聊天的窗口里豎起大拇指，你們的鼓勵和支持是支撐我的寫作計劃的強大動力，也鞭策著我不斷提高自身水平，謝謝你們！最后，感謝 [[http://www.gnu.org/software/emacs/][Emacs]] 這一世界最強大的編輯器的所有貢獻者，感謝它的插件 [[http://mwolson.org/projects/EmacsMuse.html][EmacsMuse]] 的開發(fā)者們，本文的所有編輯工作都借助這兩個卓越的自由軟件完成。謝謝你們——自由軟件社群——為社會提供了如此有生產(chǎn)力的工具。我深深欽佩你們身上體現(xiàn)出的自由軟件的精神，沒有你們的感召，我不能完成本文。在你們的影響下，采用自由文檔的方式發(fā)布本文檔，也是我對自由社會事業(yè)的微薄努力。[[Index][首頁]]--------Copyright (c)  2007  Tianyi CuiPermission is granted to copy, distribute and/or modify this document under the terms of the [[http://www.gnu.org/licenses/fdl.txt][GNU Free Documentation License]], Version 1.2 or any later version published by the Free Software Foundation.