关键词：
前言
本篇文章是我(dd_engi)正在进行中的一个雄心勃勃的写作计划的一部分，这个计划的内容是写作一份较为完善的NOIP难度的动态规划总结，名为《解动态规划题的基本思考方式》。现在你看到的是这个写作计划最先发布的一部分。
背包问题是一个经典的动态规划模型。它既简单形象容易理解，又在某种程度上能够揭示动态规划的本质，故不少教材都把它作为动态规划部分的第一道例题，我也将它放在我的写作计划的第一部分。
读本文最重要的是思考。因为我的语言和写作方式向来不以易于理解为长，思路也偶有跳跃的地方，后面更有需要大量思考才能理解的比较抽象的内容。更重要的是：不大量思考，绝对不可能学好动态规划这一信息学奥赛中最精致的部分。
你现在看到的是本文的1.0正式版。我会长期维护这份文本，把大家的意见和建议融入其中，也会不断加入我在OI学习以及将来可能的ACM-ICPC的征程中得到的新的心得。但目前本文还没有一个固定的发布页面，想了解本文是否有更新版本发布，可以在OIBH论坛中以“背包问题九讲”为关键字搜索贴子，每次比较重大的版本更新都会在这里发贴公布。
这是最基本的背包问题，每个物品最多只能放一次。
第二个基本的背包问题模型，每种物品可以放无限多次。
每种物品有一个固定的次数上限。
将前面三种简单的问题叠加成较复杂的问题。
一个简单的常见扩展。
一种题目类型，也是一个有用的模型。后两节的基础。
另一种给物品的选取加上限制的方法。
我自己关于背包问题的思考成果，有一点抽象。
试图触类旁通、举一反三。
背包的搜索
给出 USACO Training 上可供练习的背包问题列表，及简单的解答。
如果有任何意见和建议，特别是文章的错误和不足，或者希望为文章添加新的材料，可以通过http://kontactr.com/user/tianyi/这个网页联系我。
感谢以下名单：
阿坦
jason911
donglixp
他们每人都最先指出了本文第一个beta版中的某个并非无关紧要的错误。谢谢你们如此仔细地阅读拙作并弥补我的疏漏。
感谢 XiaQ，它针对本文的第一个beta版发表了用词严厉的六条建议，虽然我只认同并采纳了其中的两条。在所有读者几乎一边倒的赞扬将我包围的当时，你的贴子是我的一剂清醒剂，让我能清醒起来并用更严厉的眼光审视自己的作品。
当然，还有用各种方式对我表示鼓励和支持的几乎无法计数的同学。不管是当面赞扬，或是在论坛上回复我的贴子，不管是发来热情洋溢的邮件，或是在即时聊天的窗口里竖起大拇指，你们的鼓励和支持是支撑我的写作计划的强大动力，也鞭策着我不断提高自身水平，谢谢你们！
最后，感谢 Emacs 这一世界最强大的编辑器的所有贡献者，感谢它的插件 EmacsMuse 的开发者们，本文的所有编辑工作都借助这两个卓越的自由软件完成。谢谢你们——自由软件社群——为社会提供了如此有生产力的工具。我深深钦佩你们身上体现出的自由软件的精神，没有你们的感召，我不能完成本文。在你们的影响下，采用自由文档的方式发布本文档，也是我对自由社会事业的微薄努力。
P01: 01背包问题
题目
有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。
基本思路
这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。
用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：
f[i][v]=maxf[i-1][v],f[i-1][v-c[i]]+w[i]
这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下：“将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”，价值为f[i-1][v]；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”，此时能获得的最大价值就是f[i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。
优化空间复杂度
以上方法的时间和空间复杂度均为O(N*V)，其中时间复杂度基本已经不能再优化了，但空间复杂度却可以优化到O(V)。
先考虑上面讲的基本思路如何实现，肯定是有一个主循环i=1..N，每次算出来二维数组f[i][0..V]的所有值。那么，如果只用一个数组f[0..V]，能不能保证第i次循环结束后f[v]中表示的就是我们定义的状态f[i][v]呢？f[i][v]是由f[i-1][v]和f[i-1][v-c[i]]两个子问题递推而来，能否保证在推f[i][v]时（也即在第i次主循环中推f[v]时）能够得到f[i-1][v]和f[i-1][v-c[i]]的值呢？事实上，这要求在每次主循环中我们以v=V..0的顺序推f[v]，这样才能保证推f[v]时f[v-c[i]]保存的是状态f[i-1][v-c[i]]的值。伪代码如下：
for i=1..N
其中的f[v]=maxf[v],f[v-c[i]]一句恰就相当于我们的转移方程f[i][v]=maxf[i-1][v],f[i-1][v-c[i]]，因为现在的f[v-c[i]]就相当于原来的f[i-1][v-c[i]]。如果将v的循环顺序从上面的逆序改成顺序的话，那么则成了f[i][v]由f[i][v-c[i]]推知，与本题意不符，但它却是另一个重要的背包问题P02最简捷的解决方案，故学习只用 摘抄于-dd大牛的背包九讲P01:01背包问题题目有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。基本思路这是最基础的背包... 查看详情 背包九讲 目录 第一讲01背包问题 第二讲完全背包问题 第三讲多重背包问题 第四讲混合三种背包问题 第五讲二维费用的背包问题 第六讲分组的背包问题 第七讲有依赖的背包问题 第八讲泛化物... 查看详情 《背包九讲》 P01:01背包问题题目有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。基本思路这是最基础的背包问题，... 查看详情 背包九讲(7)有依赖的背包问题有N个物品和一个容量是V的背包。物品之间具有依赖关系，且依赖关系组成一棵树的形状。如果选择一个物品，则必须选择它的父节点。如下图所示：如果选择物品5，则必须选择物品1和2。这是因为2... 查看详情 P01:01背包问题 题目 有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。 基本思路 这是最基础的背包问... 查看详情 原文链接：https://www.cnblogs.com/jbelial/articles/2116074.htmlP01:01背包问题题目有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。... 查看详情 P01:01背包问题题目有\(N\)件物品和一个容量为\(V\)的背包。第\(i\)件物品的费用是\(c[i]\)，价值是\(w[i]\)。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。基本思路这是最基础的背包问题，特... 查看详情 本咸鱼终于停课了，在Mr.pan的支持下膜了一波背包九讲，为了方便自己以后复习，将先在的一些感悟记录下来。1.01背包 这种背包是最基础的背包，题目大概是这样： 有N件物品和一个容量为V的背包。放入第i件... 查看详情 ...//www.cnblogs.com/Christal-R/p/Dynamic_programming.html动态规划解决01背包问题一、问题描述：有n个物品，它们有各自的重量和价值，现有给定容量的背包，如何让背包里装入的物品具有最大的价值总和？二、总体思路：根据动态规划解题... 查看详情 学习自:背包九讲题目有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。基本思路:完全背包和01... 查看详情 P01:01背包问题 题目 有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。 基本思路 这是最基础的背包问题，... 查看详情 1、01背包问题。tot：总背包空间，vall[i]：每件物品的价值，w[i]：每件物品的重量http://acm.hdu.edu.cn/showproblem.php?pid=260201背包明显可以只写一维的，所以二维的就不写了。关于为什么可以只写一维的呢？这就和你枚举的顺序有关了... 查看详情 题目有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用，每件费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。基本思路:对每个物品都考虑拿几个(这个很好... 查看详情 有N件物品和一个容量是V的背包。每种物品都有无限件可用。第i件物品的体积是vi，价值是wi。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。输入格式第一行两个整数，N，V，... 查看详情 P01:01背包问题 题目 有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。 基本思路 这是最基础的背包问题，... 查看详情 1.01背包 #include<iostream>#include<cstring>usingnamespacestd;constintN=1010;intf[N];intmain()intn,m;while(cin&g 查看详情 ...典问题不牢固的原因。所有解题思路学习来源于acwing。01背包问题问题叙述： 有nnn件物品和一个容量 查看详情 目录第一讲01背包第二讲完全背包第三讲多重背包第四讲混合背包第五讲二维费用的背包问题第六讲分组背包第七讲有依赖的背包问题第八讲背包问题求方案数第一讲01背包01背包是每种武平只能选择一次，计算出最大价值的问题... 查看详情 背包九讲
背包九讲（转载，实在不知道哪个是原创了）
转载：《背包九讲》
背包九讲
背包九讲
[转]背包九讲
背包九讲（orz）
膜背包九讲有感orz
搬：背包九讲(代码片段)
第二讲完全背包问题(对背包九讲的学习)(代码片段)
直接抱过来dd大牛的《背包九讲》
背包九讲&&题目
第三讲多重背包问题(对背包九讲的学习)
背包九讲之二：完全背包问题：一个物品允许选多次(代码片段)
dd在度娘上看到的一个大牛的《背包九讲》(:
记录b站yxc的背包九讲相关代码
背包九讲整理(代码片段)
背包九讲(代码片段)