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