背包九讲 2.0

ACM暑期集训报告院系：专业：年级：学号：姓名：日期：西南交通大学目录目录 (1)第1章动态规划（dp） (2)1.1 简介 (2)1.2 教师内容 (5)1.3 基本dp——背包问题 (6)1.4若干经典dp及常见优化 (9)1.5类似题目 (10)参考文献 (31)附录1 暑期集训心得体会 (31)第1章动态规划（dp）（标题采用2号黑体居中，下空1行）1.1 简介（标题采用四号黑体，正文内容采用小四号字体，1.5倍行距）在解决问题的时候我们经常遇到这种问题：在多种方式的操作下我们如何得到一个最优的方式让我们得到满意的结果。

这时候我们大多人的思想就是贪心。

不错贪心确实是一个不错的算法，首先他简单容易想到，我们在操作起来也比较容易。

现在我推荐几道我们oj上的贪心算法的题：soj1562药品运输soj1585 Climbing mountain。

为了引入动归算法我先拿药品运输这道题简单说一下贪心算法。

示例1：药品运输（题目采用小四号Times New Roman字体）Description5.12大地震后，某灾区急需一批药品，现在有N种药品需要运往灾区，而我们的运输能力有限，现在仅有M辆运输车用来运输这批药品，已知不同的药品对灾区具有不同的作用（“作用”用一个整数表示其大小），不同的药品需要的运输力（必要的车辆运载力）不同，而不同的车辆也具有不同的运输力。

同时，我们希望不同的药品用不同的车辆来运输（避免发生混淆）。

现在请你帮忙设计一方案，来使得运往灾区的药品对灾区的作用最大。

Input第一行包含一个整数T，表示需要处理的测试数据组数。

每一组第一行包括两个整数N,M，分别表示药品总数，及车辆总数。

接着第二行包含N个整数（pi<=10000），分别表示每种药品的作用。

接着第三行包含N个整数，分别表示每种药品必须得运载力(wi<=1000)。

接着第四行包含M个整数，表示每辆车的运输力(c<=1000)；（T<=10; N,M<=1000）Output输出包括T行，每行仅一个整数，表示最大的作用值。

dp[j] = max(dp[j], dp[j - c[i]] + v[i]);
}
}
i\j
j=0
i=0
0
j=1 j=2 j=3 j=4 j=5 j=6
0
00000i=10
3
6
9
12 15 18
i=2
0
3
6
10
13 16 20
17
多重背包
有n种物品，每种最多可以取x[i]个，每个物品有大小和价值，问总大小不超过m的情况下能取到最大的 价值是多少 代码如下： for (int i = 1; i <= n; ++i) {
} } 注意此时j一定是倒序产生
16
完全背包
有n种物品，每种最多可以取无数个，每个物品有大小和价值，问总大小不超过m的情况下能取到最大 的价值是多少
01背包中第二维改成正向即可：
for (int i = 1; i <= n; ++i) {
for (int j = c[i]; j <= m; ++j) {
}
10
数字三角形
线性DP解法 for(int i=m-1;i>0;i--) {
for(int j=0;j<=i;j++) { a[i-1][j]+=max(a[i][j],a[i][j+1]);
} }
11
数字三角形
暴力递归搜索解法： int dfs(int i, int j) {
if (i == n) return a[i][j]; return max(dfs(i+1,j), dfs(i+1,j+1)) + a[i][j]; }

背包九讲P01: 01背包问题题目有N件物品和一个容量为V的背包。

第i件物品的费用是c[i]，价值是w[i]。

求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

基本思路这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。

用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。

则其状态转移方程便是：f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}。

这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。

所以有必要将它详细解释一下：“将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。

如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”，此时能获得的最大价值就是f[i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。

注意f[i][v]有意义当且仅当存在一个前i件物品的子集，其费用总和为v。

所以按照这个方程递推完毕后，最终的答案并不一定是f[N] [V]，而是f[N][0..V]的最大值。

如果将状态的定义中的“恰”字去掉，在转移方程中就要再加入一项f[i][v-1]，这样就可以保证f[N] [V]就是最后的答案。

至于为什么这样就可以，由你自己来体会了。

优化空间复杂度以上方法的时间和空间复杂度均为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]]的值。

“
背包的打法有许多种，本人只会三种，但是本人最喜欢以下的这种打法，因为它速度上虽然不如一条龙快，但是却比一条龙牢固可靠----跑5公里时如果背包垮了，那就要抱着被子跑了，多狼狈啊。

所以，”“”
还是这种打法好；速度也不算慢，反正本人在部队时紧急集合的速度通常是5分钟以内出门，还不是最快的。

下面我用实物图片教教不会打背包的兄弟，特别是那些即将去部队的新战友们，大家喜欢的话请支持一下，要是学不会你们砍我，呵呵。

有兴趣的可以拿包烟或是书练练手
一、叠被子：被子要四叠，这样打出来的背包看着才好看精干，平常整内务的三叠打出来呆头呆脑的效果不好；然后把被子折叠成图中形状
二、这是什么？原来是背包带隆重惊艳登场，我通常把它盘成圆饼状，便于存放携带，由于没有宽背包带，就不说它了
三、拆开背包带，如图竖直放在被子上
四、被子翻过来，背包带的一端插入扣里，用力拉紧；然后绕被子一圈，抽紧
五、第一大步骤完成
六、现在开始处理背包下端，用背包带的另一段斜压背包一角，绕下端一圈，抽紧
七、第二大步骤完成
八、现在处理中间，上下多出的带子交叉拉紧（用力！），绕背包一圈，抽紧
九、打结（注意一定要在背包的侧面打结，要是在背面打结的话，跑5公里硌得背部生痛，多出来的带子掖到缝隙里藏好）
十、大功告成！！漂亮不？我手头没有宽背包带，所以背包不完整，见谅！！
铁血, 本贴地址: /post_2426285_1.html。

下面总结一些小小的经验：1、组队很重要，队友们一定要能谈得来（曾经发生一组队员互相不服气，结果各自做各的，成绩就可想而知了），除此之外，队员之间一定要各有所常，建模嘛，无非就是查阅文献，建立模型，分析数据，编程，写文章，较对等等，保证你们组每个人都会有一些强项，当然男女生也应该都是要有的，所谓男女搭配，干活不累，嘿嘿;2、文章整洁很重要。

如果你是评委的话，肯定喜欢写的文章有条理，图文并茂之类的文章，将心比心，抓住评委的心才是最重要。

3、做建模创新很重要。

这么多的文章你的要想脱颖而出，创新也必须的，当然，你可以想你这篇文章结合了什么什么方法，最好把那方法说得天花乱坠，但不可华而不实，这就行啦。

4、摘要很重要。

以前大学生比赛的时候，是先通过摘要就刷一批，我觉得这是很公平的方法，摘要就是说明你这篇文章的特色和结构的，如果摘要我都不愿意看，干嘛花时间看你的正文。

5、人品很重要，还是我那句话，莫要太看重结果，抱着神马都是浮云的心态~~~数模经历入门篇平时有不少人会加我QQ，然后问诸如“什么是数模”“我该怎么学数模”之类的问题。

这里不是不鼓励大家和我讨论，而是有些问题google或baidu一下很容易得到答案，完全没有必要去问学长或老师。

而且使用搜索引擎的能力在数学建模中也是一个非常重要的能力。

这里推荐一些书，建议刚接触数学建模的朋友们看姜启源、谢金星的《数学模型》，这本书比较全面地介绍了数学建模中一些基本的、常用的模型和方法，有很多的例子，可以全面地了解什么是数学模型，也能基本地掌握如何抽象建模等。

希望进一步深入的同学推荐姜启源、谢金星的《数学模型案例集》，这本书里有不少比较有意思的问题，可以尝试自己做一下，难度比正式比赛要差很多，但是对于初学者来说比较容易上手。

也推荐叶其孝的那套黑书，虽然内容有点老，但是有很多比较有意思的解题思路等。

这里推荐一个很不错的数学建模网站：，那里有很多非常不错的学习资料。

对于那些已经有一些数学建模基础的同学则不推荐读叶其孝的那套书，而是可以直接在网上找一些往年国一或是美赛特等的文章，仔细阅读，了解其中的方法，然后自己动手重新做一遍。

p[x]
p[x]
x A B A
x B
以把一个机器人的移动路线改为 p[x]→x→A→x→B→x→p[x]，另一个机器人则是停在 p[x]， 效果相同，但(p[x], x)这条边可以少走两次，于是我们就得到了一个更优的方案。经过这个 转化后，可以发现算法一中的 f[x][i][j]和 g[n][i][j]都只需要计算满足 0≤j≤1 的状态。 于是，这个算法的空间复杂度降到了 O(2NK)=O(NK)。在计算 g[n][i][j]时需要枚举 i0、 j0、jn（in 可以直接计算出来） ，所以转移的时间为 O(4K)，而状态数为 O(2NK)，所以每做一 次动态规划的时间复杂度为 O(8NK2)，总的时间复杂度为 O(8N2K2)=O(N2K2)。这个算法的常 数是比较大的，期望得分为 35 分。 【算法三】 如果要枚举根的话，算法二达到的 O(N2K2)的时间复杂度已经很难再降低了，只是过大 的常数影响了算法的效率。这里考虑有没有常数较小的算法也能达到这个时间复杂度。 观察算法一原始的状态转移方程：
g[n][i][ j] min{ f [ x1 ][i1 ][ j1 ] f [ x2 ][i2 ][ j2 ] …… f [ xn ][in ][ jn ]}
其中 jk≤ik≤i， i i1 j1 i2 j2 …… in jn j 。不难发现这个式子和前面的式子 很像，因为这就是利用 g 来存储中间结果以避免重复计算。状态转移方程为
i j (i1 j1 ) (i2 j2 ) …… (im jm )
这启 ik jk 代表了什么呢？不难发现就是最后停在以 xk 为根的子树中的机器人的个数。 发我们从“最后每棵子树内停了多少个机器人”入手。 在对一些例子进行分析之后，可以发现另一个性质：在最优方案中，如果有至少 2 个机 器人进入了以 x 为根的子树，那么这些机器人都应该停在以 x 为根的子树内。证明如下：

7.3完全背包问题79
7.4多重背包问题79
7.5二维费用的背包问题80
7.6分组的背包问题81
7.7有依赖的背包问题81
7.8泛化物品81
7.9混合背包问题82
7.10特殊要求82
7.11背包问题的搜索解法83
7.12子集和问题84
第八单元 排序算法85
8.1常用排序算法85
8.2简单排序算法87
11.6进制转换（正整数）123
11.7高精度算法（压位存储）!123
11.8快速幂!128
11.9表达式求值129
11.10解线性方程组*133
第十二单元 数论算法135
12.1同余的性质!135
12.2最大公约数、最小公倍数!135
12.3解不定方程ax＋by＝c!*135
12.4同余问题*136
13.8拓扑排序152
13.9关键路径155
13.10二分图初步157
13.11小结160
第十四单元STL简介164
14.1STL概述164
14.2常用容器164
14.3容器适配器170
14.4常用算法171
14.5迭代器175
14.6示例：合并果子175
附录A思想和技巧177
A.1时间/空间权衡177
1.9简单的算法分析和优化14
1.10代码编辑器16
第二单元 基础算法17
2.1经典枚举问题17
2.2火柴棒等式18
2.3梵塔问题19
2.4斐波那契数列19
2.5常见的递推关系!20
2.6选择客栈22
2.72k进制数23
2.8Healthy Holsteins24
2.9小结25

如果并没有要求必须把背包装满，而是只希望价格尽量大，初始化时应该将 f[0..V]全部设 为 0。
为什么呢？可以这样理解：初始化的 f 数组事实上就是在没有任何物品可以放入背包时的合 法状态。如果要求背包恰好装满，那么此时只有容量为 0 的背包可能被价值为 0 的 nothing“恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，它们的值就都 应该是-∞了。如果背包并非必须被装满，那么任何容量的背包都有一个合法解“什么都不 装”，这个解的价值为 0，所以初始时状态的值也就全部为 0 了。
前言
本篇文章是我(dd_engi)正在进行中的一个雄心勃勃的写作计划的一部分，这个计划的内容是 写作一份较为完善的 NOIP 难度的动态规划总结，名为《解动态规划题的基本思考方式》。现 在你看到的是这个写作计划最先发布的一部分。
背包问题是一个经典的动态规划模型。它既简单形象容易理解，又在某种程度上能够揭示动 态规划的本质，故不少教材都把它作为动态规划部分的第一道例题，我也将它放在我的写作 计划的第一部分。
这个小技巧完全可以推广到其它类型的背包问题，后面也就不再对进行状态转移之前的初始 化进行讲解。
小结
01 背包问题是最基本的背包问题，它包含了背包问题中设计状态、方程的最基本思想，另 外，别的类型的背包问题往往也可以转换成 01 背包问题求解。故一定要仔细体会上面基本思 路的得出方法，状态转移方程的意义，以及最后怎样优化的空间复杂度。
感谢 XiaQ，它针对本文的第一个 beta 版发表了用词严厉的六条建议，虽然我只认同并采纳 了其中的两条。在所有读者几乎一边倒的赞扬将我包围的当时，你的贴子是我的一剂清醒 剂，让我能清醒起来并用更严厉的眼光审视自己的作品。
当然，还有用各种方式对我表示鼓励和支持的几乎无法计数的同学。不管是当面赞扬，或是 在论坛上回复我的贴子，不管是发来热情洋溢的邮件，或是在即时聊天的窗口里竖起大拇 指，你们的鼓励和支持是支撑我的写作计划的强大动力，也鞭策着我不断提高自身水平，谢 谢你们！

NOIP复习资料（C++版）主编葫芦岛市一高中李思洋完成日期2012年8月27日……………………………………………………………最新资料推荐…………………………………………………前言有一天，我整理了NOIP的笔记，并收集了一些经典算法。

不过我感觉到笔记比较凌乱，并且有很多需要修改和补充的内容，于是我又搜集一些资料，包括一些经典习题，在几个月的时间内编写出了《NOIP复习资料》。

由于急于在假期之前打印出来并分发给同校同学（我们学校既没有竞赛班，又没有懂竞赛的老师。

我们大家都是自学党），《NOIP复习资料》有很多的错误，还有一些想收录而未收录的内容。

在“减负”的背景下，暑期放了四十多天的假。

于是我又有机会认真地修订《NOIP复习资料》。

我编写资料的目的有两个：总结我学过（包括没学会）的算法、数据结构等知识；与同学共享NOIP知识，同时使我和大家的RP++。

大家要清醒地认识到，《NOIP复习资料》页数多，是因为程序代码占了很大篇幅。

这里的内容只是信息学的皮毛。

对于我们来说，未来学习的路还很漫长。

基本假设作为自学党，大家应该具有以下知识和能力：①能够熟练地运用C++语言编写程序（或熟练地把C++语言“翻译”成Pascal语言）；②能够阅读代码，理解代码含义，并尝试运用；③对各种算法和数据结构有一定了解，熟悉相关的概念；④学习了高中数学的算法、数列、计数原理，对初等数论有一些了解；⑤有较强的自学能力。

代码约定N、M、MAX、INF是事先定义好的常数（不会在代码中再次定义，除非代码是完整的程序）。

N、M、MAX 针对数据规模而言，比实际最大数据规模大；INF针对取值而言，是一个非常大，但又与int的最大值有一定差距的数，如100000000。

对于不同程序，数组下标的下限也是不同的，有的程序是0，有的程序是1。

阅读程序时要注意。

阅读顺序和方法没听说过NOIP，或对NOIP不甚了解的同学，应该先阅读附录E，以加强对竞赛的了解。

代码：
procedure MultiplePack(cost,weight,amount)
if cost*amount>=V
CompletePack(cost,weight)
return
integer k=1
while k<amount
ZeroOnePack(k*cost,k*weight)
amount=amount-k
f[j*v+k]:=b[l]+j*w; //用队列头的值更新f[j*v+k]
end;
end;
end;
writeln(f[m]);
end.
题目：砝码秤重，tyvj1086，zoj2156，poj2392，hdu1085
Poj1014，divide（见dp2）
二维费用背包
就是限制条件多了一个，变成了二维容量，从而状态多了一维而已。
题目：hdu3236，打包（见dpset）poj2184
分组背包
有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
这个问题变成了每组物品有若干种策略：是选择本组的某一件，还是一件都不选。也就是说设f[k][v]表示前k组物品花费费用v能取得的最大权值，则有:f[k][v]
for i:=1 to n do
begin
read(v,w,c); //读入当前物品：v为物品体积、w为物品价值、c为物品可用次数
if m div v<c k:=0 to v-1 do //把所有的体积按除以v的余数划分为0~v-1

1.你让工人为你工作7天，回报是一根金条，这个金条平分成相连的7段，每天结束的时候,工人会向你要一段金条。

如果只允许你两次把金条弄断，你如何给你的工人付费？2.有1000个苹果，将它们放在100个箱子里，怎么放才能让我向你要苹果的时候，你都能整箱整箱的给我,你的给法是否唯一?这两个题目我想很多人都曾做过，如果你会做第一个题目，那你也应该会做第二个...如果不会,请看文章标题的提示...下面就个人理解给出这种二进制的思想:我第一次看到的是第二个题目，一开始，没什么思路，只是一步步的试，比如说，如果要一个苹果，我就必须要有一个箱子里放1个苹果，这是没法改的，如果要两个苹果，我要么是给一个放有2个苹果的箱子，要么是给两个各放有1个苹果的箱子，显然后面那种不行，因为当向我们要三个苹果的时候，我们至少要用掉三个箱子...后来突然想到高中涂高考志愿卡时,遇到的一个有趣的1248码,卡片只给出四个涂色框,第一个表示1第二个表示2,第三个表示4,第四个表示8,如果我们的号码中有个数字是7,我们就将1 2 4都涂上.很好,由1,2,4,8这几个数字,我们可以看出,它们能组成1-15中的任何一个数字,如果我们就用这种方法,用掉4个箱子,那第五个箱子,我们就必须要放16个苹果,这样一来,可以组成1-31中的任何一个数字,第六个箱子我们得放32个...依此类推,我们放的是1,2,4,8,16,32...惊讶的发现:这组数字的规律是一个以2为比的等比递增数列,自然而然想到二进制化十进制的方法,11111111B=2的7次幂+2的6次幂+2的5次幂+2的4次幂+... 如此一来,如果我们让每个箱子各对应一个具有10bit的二进制的一位,1表示在第n个箱子放2的n次幂个苹果,我们可以算出,0000000000B~1111111111B的表数范围为:0-1023,而且可以看出,每一个在这中间的数都可以唯一的对应一个二进制数,也就是说针对不同数目的苹果,我们给箱子的时候,只有一种给法,因为只有1000个苹果,所以最后一个箱子我们没有放512个苹果,而是只放了489个,那么1-488只有唯一的给法,489-1000有两种给法.(更正一下:只有489-511有两种给法...1-488和512-1000都只有唯一的给法...)显然,第一个题目也是用到了这种思想,我们可以将金条分成1、2、4三段,不管哪天工人向我们要金条,我们都能给他,比如说:工人第一天没有要金条,第二天要的时候,我们给他2段,第三天他没有要,第四天他要我们给金条,于是我们将那块四段的给他,收回那个2段的...二进制思想和多重背包问题二进制思想问题描述：假设有1000个苹果，现在要取n个苹果，如何取？正常的做法应该是将苹果一个一个拿出来，直到n个苹果被取出来。

背包
By @wgx998877
九 讲
Copy right@中国地质大学（北京）ACM/ICPC 集训队
背包问题及其变化
完全背包
01背包 ZeroOnePack
CompletePack
混合背包 MixedPack
MultiplePack
多重背包
二维费用背包 泛化物品 有依赖背包 分组背包
有N件物品和一个容量为V的背包。第i件物 品的费用是c[i]，价值是w[i]。求解将哪些物 品装入背包可使价值总和最大。
void OneZeroPack(int cost,int value){ int i,j; for(i = total;i >= cost; i--) f[i] = max(f[i],f[i-cost]+value); }
逆序！ 这就是关键！ 1 for i=1..N 2 for v=V..0 3 f[v]=max {f[v],f[v-c[i]]+w[i]}; 4 分析上面的代码：当内循环是逆序时 就可以保证后一个f[v]和f[v-c[i]]+w[i]是前一状态的！ 这里给大家一组测试数据： 测试数据： 10,3 3,4 4,5 5,6
二维费用背包
有依赖背包
分组背包
for i=1..N if //第i件物品属于01背包 ZeroOnePack(c[i],w[i]) else if //第i件物品属于完全背包 CompletePack(c[i],w[i]) else if //第i件物品属于多重背包 MultiplePack(c[i],w[i],n[i])
混合背包 MixedPack
MultiplePack
多重背包
for (i = 1; i < N; ++i) { if (cost[i] * amount[i] >= V) { CompletePack(cost[i], weight[i]); return; } int k = 1; while (k < amount[i]) { ZeroOnePack(k*cost[i], k*weight[i]); amount[i] = amount[i] - k; k = k*2; } ZeroOnePack(amount[i]*cost[i], amount[i]*weight[i]); }

背包问题九讲目录第一讲 01背包问题第二讲完全背包问题第三讲多重背包问题第四讲混合三种背包问题第五讲二维费用的背包问题第六讲分组的背包问题第七讲有依赖的背包问题第八讲泛化物品第九讲背包问题问法的变化附：USACO中的背包问题前言本篇文章是我(dd_engi)正在进行中的一个雄心勃勃的写作计划的一部分，这个计划的内容是写作一份较为完善的NOIP难度的动态规划总结，名为《解动态规划题的基本思考方式》。

现在你看到的是这个写作计划最先发布的一部分。

背包问题是一个经典的动态规划模型。

它既简单形象容易理解，又在某种程度上能够揭示动态规划的本质，故不少教材都把它作为动态规划部分的第一道例题，我也将它放在我的写作计划的第一部分。

读本文最重要的是思考。

因为我的语言和写作方式向来不以易于理解为长，思路也偶有跳跃的地方，后面更有需要大量思考才能理解的比较抽象的内容。

更重要的是：不大量思考，绝对不可能学好动态规划这一信息学奥赛中最精致的部分。

你现在看到的是本文的1.0正式版。

我会长期维护这份文本，把大家的意见和建议融入其中，也会不断加入我在OI学习以及将来可能的ACM-ICPC的征程中得到的新的心得。

但目前本文还没有一个固定的发布页面，想了解本文是否有更新版本发布，可以在OIBH论坛中以“背包问题九讲”为关键字搜索贴子，每次比较重大的版本更新都会在这里发贴公布。

目录第一讲 01背包问题这是最基本的背包问题，每个物品最多只能放一次。

第二讲完全背包问题第二个基本的背包问题模型，每种物品可以放无限多次。

第三讲多重背包问题每种物品有一个固定的次数上限。

第四讲混合三种背包问题将前面三种简单的问题叠加成较复杂的问题。

第五讲二维费用的背包问题一个简单的常见扩展。

第六讲分组的背包问题一种题目类型，也是一个有用的模型。

后两节的基础。

第七讲有依赖的背包问题另一种给物品的选取加上限制的方法。

第八讲泛化物品我自己关于背包问题的思考成果，有一点抽象。

背包之01背包、完全背包、多重背包详解首先说下动态规划，动态规划这东西就和递归一样，只能找局部关系，若想全部列出来，是很难的，比如汉诺塔。

你可以说先把除最后一层的其他所有层都移动到2，再把最后一层移动到3，最后再把其余的从2移动到3，这是一个直观的关系，但是想列举出来是很难的，也许当层数n=3时还可以模拟下，再大一些就不可能了，所以，诸如递归，动态规划之类的，不能细想，只能找局部关系。

1.汉诺塔图片（引至杭电课件:DP最关键的就是状态，在DP时用到的数组时，也就是存储的每个状态的最优值，也就是记忆化搜索）要了解背包，首先得清楚动态规划：动态规划算法可分解成从先到后的4个步骤：1. 描述一个最优解的结构；2. 递归地定义最优解的值；3. 以“自底向上”的方式计算最优解的值；4. 从已计算的信息中构建出最优解的路径。

其中步骤1~3是动态规划求解问题的基础。

如果题目只要求最优解的值，则步骤4可以省略。

背包的基本模型就是给你一个容量为V的背包在一定的限制条件下放进最多(最少?)价值的东西当前状态以前状态看了dd大牛的《背包九讲》01背包，完全背包，多重背包这三者的使用和区别，部分会引用dd大牛的《背包九讲》，如果有错，欢迎指出。

(留言即可)首先我们把三种情况放在一起来看：01背包（ZeroOnePack）: 有N件物品和一个容量为V的背包。

（每种物品均只有一件）第i件物品的费用是c[i]，价值是w[i]。

求解将哪些物品装入背包可使价值总和最大。

完全背包(CompletePack): 有N种物品和一个容量为V的背包，每种物品都有无限件可用。

第i种物品的费用是c[i]，价值是w[i]。

求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

多重背包(MultiplePack): 有N种物品和一个容量为V的背包。

第i种物品最多有n[i]件可用，每件费用是c[i]，价值是w[i]。

求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

怎么学动规对于信息学竞赛的选手们来说，动态规划是一个既熟悉又陌生的名字。

曾几何时，我们望着这个生僻的名词一筹莫展，又几何时，我们因为发现了它的美妙而欢呼雀跃。

在这里，我就结合自己的些许经验来谈谈信息学选手对于动态规划的学习。

什么是动态规划动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。

20世纪50年代初美国数学家R.E.Bellman 等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。

--百度百科以上的解释或许过于专业，在高中的信息学竞赛中，我们可以把动态规划理解为将一个问题的求解过程分为几个部分，并逐一求得最优值，从而得到全局最优值的方法。

举个简单的例子来说明：假设我们要以最高的利润卖出某样物品，我们就可以把整个过程分为两个部分——进货和销售。

如果能以最低的价格进货，以最高的价格出手。

毫无疑问，我们便可以得到最高的利润。

动态规划在竞赛中的历史在信息学竞赛短暂的历史中，伴随着计算机科学领域的突飞猛进，算法和数据结构的难度和广度都不断地发展，从平衡树网络流，新的算法和数据结构不断地被纳入大纲。

动态规划无疑是其中一颗璀璨的明星，在信息学竞赛的舞台上绽放出夺目的光彩。

IOI94的《数字三角形》，第一次将动态规划这个名词刻进了信息学竞赛的历史。

而NOI 历史上的第一道动态规划题目出自NOI95的《石子归并》。

自此之后，动态规划就一发而不可收拾，成为了近年来NOIP 、NOI 以及IOI 必需掌握的内容。

动态规划的条件任何一个算法都有其局限性，同样，不是每一个问题都可以动态规划解决的。

关于动态规划的条件我们参考以下方奇在2000年国家集训队中的描述：1 最优化原理最优化原理可这样阐述：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。