背包问题学习笔记（从入门到再入门直到精通）

01背包

01背包一般有三种问法：
问题1.问能否凑出某些数
问题2.问凑出某些数的方案数
问题3.问最大收益（这里面又有刚好装满和没有刚好装满的区别）
这三种问法其实是都可以归入第一个问题的
（从二维转一维的过程就不细讲了，可以画图理解，这里讲一维方程的另一种理解方式）

问题1：

有n根木棍(0≤n≤30)，从中选若干根使得它们的 长度和s 最接近v(正整数，0≤v≤20000)，且s<=v。
【输入格式】
一个整数v，一个整数n。接下来n个整数，分别表示这n根木棍的长度。
【输出格式】
一个整数，表示v-s。

这时我们先来一段模拟：
假设有10个背包，体积为1~10，有两个物品，体积为1和5
现在体积为1的物品去填充背包，若它从前往后按如下方式填充（博主抽风警告）：
当看到体积为1的背包时：(ｷ｀ﾟДﾟ´)!!，刚刚合我的口味，填进去！
当看到体积为2的背包时：（回头看体积为1的背包，好像得了健忘症一样），那个体积为1的背包已经被某个家伙填进去了，若那个家伙过来，就可以和我一起填满体积为2的背包了！那这个背包就算是被填了吧！
当看到体积为2的背包时：回头看体积为2的背包，好像得了健忘症一样……（后面过程自行脑补）
最后，1这个逗比就把背包填成了这个样子：

但是它并没有意识到，它将自己反复用了多次诶！
但假设它从后向前填充：
当看到体积为10的背包时：（回头看体积为9的背包），那个体积为9的背包还没有被填，这个也填不了
……
当看到体积为1的背包时：终于找到一个合我口味的了，填进去
这时的背包被填成了这样：

这就是我们想要的结果啊，本来在题设里面1这个数就只能用一次嘛
这就是01背包和完全背包的本质区别，也是只有01背包可以用倒序的原因
通过上面的模拟，我们对于问题1的算法也就大概出来了：让每一个物品按倒序对各个背包做贡献
因此这道题,我们将木棍长度看做物体体积，那么问题就转化为求小于等于v的最大的可以被表示的数
设f[i]表示i能否被表示，则核心代码：

for(int i=1;i<=n;++i){
	for(int j=V;j>=w[i];--j){
		f[i]=f[i]|f[i-w[i]];
	}
}

问题2：

有n根木棍(0≤n≤30)，求用这些木棍拼出长度为W的木棍的方案数
【输入格式】
一个整数W，一个整数n。接下来n个整数，分别表示这n根木棍的长度。
【输出格式】
一个整数，表示方案数。

这个问题其实就是上一个问题的小变式
上面的模拟过程中，当一种体积的背包可以被凑出来的时候，就意味着这种体积的背包又多了几种拼凑方法，根据加法原理，设f[i]为长度为i的小木棍的方案数，则

for(int i=1;i<=n;++i){
	for(int j=V;j>=w[i];--j){
		f[j]+=f[j-w[i]];//f数组初始值为极大值，f[0]的初值为0，这是根据定义推出的需求
	}
}

问题3：

其实一般的背包问题，问的最多的就是问题3
但是这个问题3其实还是问题1的小变种
当体积为i的物品可以放入体积为j的背包时，这个物品就有权更新这个背包收益的最大值（当然不一定成功，因为总是可能有比它更大的）
于是就让他去更新吧：

for(int i=1;i<=n;++i){
	for(int j=V;j>=w[i];--j){
		f[j]=max(f[j],f[j-w[i]]+c[i]);
	}
}

这时有两种不同的问法，一种是求刚刚装满的最大收益，另外一种是不一定要装满的最大收益
这之间的区别还是用模拟来理解：
假设有两个相同的物品：体积和收益都为3
当第一个物品从后往前填的时候：
假设f数组初值为0
在体积为10的背包：（回头看j-w[i]=7的背包）最大收益为0…好吧，f[10]=0+c[i]=3
……
在体积为2的背包：装不下了，走人
这时是这样的：
但当f数组初值为-inf（负无穷大）时，第一个物品还是会去填，但是-inf+3=-inf，所以填出来是这样的：

这就是两种问法的不同，对于后面的其他背包也是一样的
这种办法也可以理解为：-inf不允许非恰好的值更新

例题

信息学奥赛一本通_01背包问题

【题目描述】
一个旅行者有一个最多能装 M
公斤的背包，现在有 n 件物品，它们的重量分别是W1，W2，…,Wn,它们的价值分别为C1,C2,…,Cn，求旅行者能获得最大总价值。
【输入】
第一行：两个整数，M
(背包容量，M≤200)和N(物品数量，N≤30)；
第2…N+1
行：每行二个整数Wi，Ci，表示每个物品的重量和价值。
【输出】
仅一行，一个数，表示最大总价值。

信息学奥赛一本通_采药

【题目描述】
辰辰是个很有潜能、天资聪颖的孩子，他的梦想是称为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”如果你是辰辰，你能完成这个任务吗？
【输入】
输入的第一行有两个整数T（1≤T≤1000）和M（1≤M≤100），T代表总共能够用来采药的时间，M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之间（包括1和100）的的整数，分别表示采摘某株草药的时间和这株草药的价值。
【输出】
输出只包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。

luoguP1060_开心的金明

题目描述
金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。 更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N 元钱就行”。 今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的N 元。 于是，他把每件物品规定了一个重要度，分为5等：用整数1 ~5 表示，第5 等最重要。 他还从因特网上查到了每件物品的价格（都是整数元）。 他希望在不超过N 元（可以等于N 元）的前提下，使每件物品的价格与重要度的乘积的总和最大。
设第j件物品的价格为v[j] ，重要度为w[j] ，共选中了k 件物品，编号依次为j1 ，j2 ，……，jk ，则所求的总和为：v[j1]∗w[j1]+v[j2]∗w[j2]+…+v[jk]∗w[jk] 。（其中∗ 为乘号）
请你帮助金明设计一个满足要求的购物单。
[输入输出格式]
输入格式：
输入的第1 行，为两个正整数，用一个空格隔开：
N m （其中N (<30000 ）表示总钱数，m （<25 ）为希望购买物品的个数。）
从第2 行到第m+1 行，第j 行给出了编号为j−1 的物品的基本数据，每行有2 个非负整数
v p （其中v 表示该物品的价格(v<=10000) ，p表示该物品的重要度(1 ~5) )
输出格式：
输出只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（<100000000 ）。

完全背包

上面的模拟过程中我们可以看到，完全背包和01背包只有一步之遥，因此：

for(int i=1;i<=n;++i){
	for(int j=w[i];j<=V;++j){
		f[j]=max(f[j],f[j-w[i]]+c[i]);
	}
}

即可
统计方案数和可行性也是同理，改一下循环顺序就可以了
完全和01背包的时间复杂度都是O(nV)
注意，对于二维的完全背包，上面代码中的两层循环可以变，但是对于一维的就不行，因为这样子的话f[i-v[j]]和f[i]实质上已经不是同一层的了

二进制优化

但是这里不得不提一个二进制优化
不难知道，任何一个正整数都可以被0和1在二进制下表示，也就意味着任意一个非负整数X，将其按照二进制下按权展开，有：

$X=k0\times{2}^{0}+k1\times{2}^{1}+k2\times{2}^{2}...+kn\times{2}^{n}$X=k0×20+k1×21+k2×22...+kn×2n

因此，对于完全背包，我们可以用这种二进制的思想来将其转化为01背包然后用01背包的代码来解决
考虑将体积为V，质量为W的这种物品拆成（体积，质量）：（1V，1W）,（2V，2W），（4V，4W），（8V，8W）……（${2}^{n}V$2nV，${2}^{n}W$2nW）这样的n个物品，这样拆分的话就可以用这些物品表示某个范围内的所有物品了：如选6个物品，可以用一个（4V，4W）和一个（2V，2W）

这时我们要得到这个n的值：
假设背包体积为V，这项物品单个体积为w，假设我们拆了n个物品，那么这n个物品能够表示的最大物品的体积就是：
$Vmax=w(\frac{{2}^{0}(1-{2}^{n})}{1-2})=w({2}^{n}-1)$Vmax=w(1−220(1−2n)​)=w(2n−1)（等比数列求和）
而在实际问题中，这种物品选最多的情况就是这种物品将背包装满，即：
$Vmax=V=w({2}^{n}-1)$Vmax=V=w(2n−1)
于是可以得到
$n=log_{2}{((V/w)-1)}$n=log2​((V/w)−1)
因此，在体积为V的背包中，对于一种重量为w的物品，我们可以将其拆成$log_{2}{(V/w)+1}$log2​(V/w)+1个物品，根据二进制的思想，我们可以用这些物品表示从体积为1~V的所有决策（具体证明可以分类讨论，由于最后会有一块剩余不能被以${2}^{n}$2n的方式拆分，就以这个值为分界线讨论大于其的值能不能被表示和小于其的值能不能被表示）

这样拆分后的时间复杂度为O( $V\times\sum_{i=1}^{n}({log_{2}{(V/w[i])+1}})$V×∑i=1n​(log2​(V/w[i])+1) )

虽然这样拆分不能是完全背包的时间复杂度变得更优，但是这为后面的多重背包和混合背包提供了一种解决问题的思路

例题

信息学奥赛一本通_完全背包问题

【题目描述】
设有n
种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，最大载重量为M，今从n种物品中选取若干件(同一种物品可以多次选取)，使其重量的和小于等于M，而价值的和为最大。
【输入】
第一行：两个整数，M
(背包容量，M≤200)和N(物品数量，N≤30)；
第2…N+1
行：每行二个整数Wi,Ci，表示每个物品的重量和价值。
【输出】
仅一行，一个数，表示最大总价值。

信息学奥赛一本通_货币系统

【题目描述】
给你一个n种面值的货币系统，求组成面值为m的货币有多少种方案。
【输入】
第一行为n和m。
【输出】
一行，方案数。

luoguP2722_总分_Score_Inflation

题目描述
我们可以从几个种类中选取竞赛的题目,这里的一个”种类”是指一个竞赛题目的集合,解决集合中的题目需要相同多的时间并且能得到相同的分数。你的任务是写一个程序来告诉USACO的职员,应该从每一个种类中选取多少题目,使得解决题目的总耗时在竞赛规定的时间里并且总分最大。输入包括竞赛的时间,M(1 <= M <= 10,000)(不要担心,你要到了训练营中才会有长时间的比赛)和N,”种类”的数目1 <= N <= 10,000。后面的每一行将包括两个整数来描述一个”种类”:
第一个整数说明解决这种题目能得的分数(1 <= points <= 10000),第二整数说明解决这种题目所需的时间(1 <= minutes <= 10000)。
你的程序应该确定我们应该从每个”种类”中选多少道题目使得能在竞赛的时间中得到最大的分数。
来自任意的”种类”的题目数目可能是任何非负数(0或更多)。
计算可能得到的最大分数。
[输入输出格式]
输入格式：
第 1 行: M, N–竞赛的时间和题目”种类”的数目。
第 2-N+1 行: 两个整数:每个”种类”题目的分数和耗时。
输出格式：单独的一行包括那个在给定的限制里可能得到的最大的分数。

luogu【USACO08NOV】买干草Buying_Hay

约翰的干草库存已经告罄，他打算为奶牛们采购H(1≤H≤50000)镑干草.
他知道N(1≤N≤100)个干草公司，现在用1到N给它们编号.第i公司卖的干草包重量 为Pi(1≤Pi≤5,000) 磅，需要的开销为Ci(1≤Ci≤5,000) 美元.每个干草公司的货源都十分充足， 可以卖出无限多的干草包.
帮助约翰找到最小的开销来满足需要，即采购到至少H镑干草.
输入格式：
*Line 1: N 和 H
*Lines 2…N+1:两个整数P_i and C_i
输出格式：
*Line 1: 输出最小开销

这道题很有意思

信息学奥赛一本通_买书

题目描述
小明手里有n元钱全部用来买书，书的价格为10元，20元，50元，100元。
问小明有多少种买书方案？（每种书可购买多本）
【输入】
一个整数 n，代表总共钱数。（0 ≤ n ≤ 1000）
【输出】
一个整数，代表选择方案种数。

多重背包

多重背包就是：有n种物品，每种物品可以用s次，每一种物品有一个收益，有一个体积为V的背包，求装进包包的最大收益
不难看出，多重背包，就是01背包的一个扩展版，反过来说，01背包就是多重背包的一种特殊情况（s==1）

转化为最弱的01背包求解

每一种物品，我们把它拆成s个一样的物品，然后用01背包来解决：

#define loop(i,start,end) for(register int i=start;i<=end;++i)
#define anti_loop(i,start,end) for(register int i=start;i>=end;--i)
loop(i,1,n){
	anti_loop(k,m,0){
		loop(j,0,num[i]){
			if(k-v[i]*j<0)break; 
			f[k]=max(f[k],f[k-v[i]*j]+w[i]*j);
		}
	}
}

注意：虽然这个暴力打过的人很少，但是还是要注意它的枚举顺序，不能把枚举物品个数那个循环放在枚举体积的外面了，否则会导致某些物美价廉的物品被用的次数多于其总数
这样的时间复杂度为$O(V\times \sum_{i=1}^{n}{s[i]})$O(V×∑i=1n​s[i])，显然当s比较大时，这种操作是会炸的

二进制优化

二进制分析

这时我们就想到用二进制优化，将每种物品拆成二进制下的物品，这样就大大的减少了物品个数
具体来讲，对于有s个可用物品的一种物品，依照前面完全背包推导的思路，可以得到
${2}^{n}-1=s$2n−1=s
即
$n=log_{2}(s+1)$n=log2​(s+1)
即把k件物品拆成了$log_{2}(s+1)$log2​(s+1)件物品，这样的时间复杂度为
$O(V\times \sum_{i=1}^{n}log_{2}(s[i]+1))$O(V×∑i=1n​log2​(s[i]+1))，相比起$O(V\times \sum_{i=1}^{n}{s[i]})$O(V×∑i=1n​s[i])来说快了很多，特别是在数据大的时候

二进制优化代码实现

1.拆分物品

#define loop(i,start,end) for(register int i=start;i<=end;++i)
#define anti_loop(i,start,end) for(register int i=start;i>=end;--i)
loop(i,1,n){
	int v,w,s,t=1;//t变量是用来记录当前已经拆到2的多少次方的数的
	read(v),read(w),read(s);
	while(t<=s){
		V[++nl]=v*t;
		W[nl]=w*t;
		s-=t;t*=2;
	}V[++nl]=v*s,W[nl]=w*s;//最后可能还有剩余没法拆完，于是就将剩下的作为一个物体放进去
}clean(f,0);

2.01背包解决问题

#define loop(i,start,end) for(register int i=start;i<=end;++i)
#define anti_loop(i,start,end) for(register int i=start;i>=end;--i)
loop(i,1,nl){//nl是新拆分后的数据个数
	anti_loop(j,m,V[i]){
		f[j]=max(f[j],f[j-V[i]]+W[i]);
	}
}printf("%d\n",f[m]);

单调队列优化多重背包（还没学懂，留坑待补）

例题

信息学奥赛一本通_庆功会

【题目描述】
为了庆贺班级在校运动会上取得全校第一名成绩，班主任决定开一场庆功会，为此拨款购买奖品犒劳运动员。期望拨款金额能购买最大价值的奖品，可以补充他们的精力和体力。
【输入】
第一行二个数n(n≤500)，m(m≤6000)，其中n代表希望购买的奖品的种数，m表示拨款金额。
接下来n行，每行3个数，v、w、s，分别表示第I种奖品的价格、价值（价格与价值是不同的概念）和能购买的最大数量（买0件到s件均可），其中v≤100，w≤1000，s≤10。
【输出】
一行：一个数，表示此次购买能获得的最大的价值（注意！不是价格）。

混合背包

混合背包就是混合的背包，一般这样出题：

• 01+完全
• 多重+完全
• 01+多重
• 完全+01+多重
• ……
  有点暴力是吧，解决它的办法也很暴力，就是直接用二进制拆分将其全部拆成01背包然后用01背包搞掉

例题

luoguP1833_樱花

【题目描述】
爱与愁大神后院里种了n棵樱花树，每棵都有美学值Ci。爱与愁大神在每天上学前都会来赏花。爱与愁大神可是生物学霸，他懂得如何欣赏樱花：一种樱花树看一遍过，一种樱花树最多看Ai遍，一种樱花树可以看无数遍。但是看每棵樱花树都有一定的时间Ti。爱与愁大神离去上学的时间只剩下一小会儿了。求解看哪几棵樱花树能使美学值最高且爱与愁大神能准时（或提早）去上学。
【输入输出格式】
输入格式：
共n+1行：
第1行：三个数：现在时间Ts（几点：几分），去上学的时间Te（几点：几分），爱与愁大神院子里有几棵樱花树n。
第2行~第n+1行：每行三个数：看完第i棵树的耗费时间Ti，第i棵树的美学值Ci，看第i棵树的次数Pi（Pi=0表示无数次，Pi是其他数字表示最多可看的次数Pi）。
输出格式：
只有一个整数，表示最大美学值。

题解

二维费用背包

二维费用背包，就是在01背包的基础上加上了一维限制，如：有体积为V的背包，你一共有X元钱，每个物品有对应的体积和价钱和收益，问你在不透支和背包可以装得下的情况下可以取得的最大收益

方程

一般来说，如果原来的方程不能满足新问题的限制，那么就可以在原来的方程上加上一维来满足限制，这里也是一样
在01背包的方程上加上一维可以得到：设$f[i][j][k]$f[i][j][k]为前i个物品放入体积为j的背包且消耗k元的最大收益，则
$f[i][j][k]=max(f[i-1][j][k],f[i-1][j-V[i]][k-C[i]]+w[i])$f[i][j][k]=max(f[i−1][j][k],f[i−1][j−V[i]][k−C[i]]+w[i])
这时，我们可以借用01背包降维的思想，去掉第一维，得到：
$f[j][k]=max(f[j][k],f[j-V[i]][k-C[i]]+w[i])$f[j][k]=max(f[j][k],f[j−V[i]][k−C[i]]+w[i])
同样的，正序和倒序按照题目要求来定

例题

luoguP1910_L国的战斗之间谍

题目背景
L国即将与I国发动战争！！
题目描述
俗话说的好：“知己知彼，百战不殆”。L国的指挥官想派出间谍前往I国，于是，选人工作就落到了你身上。
你现在有N个人选，每个人都有这样一些数据：A（能得到多少资料）、B（伪装能力有多差）、C（要多少工资）。已知敌人的探查间谍能力为M（即去的所有人B的和要小于等于M）和手头有X元钱，请问能拿到多少资料？
输入输出格式
输入格式：
N M X
A1 B1 C1
A2 B2 C2
………………
AN BN CN
输出格式：
能得到的资料总数

luoguP1507_NASA的食物计划

题目背景
NASA(美国航空航天局)因为航天飞机的隔热瓦等其他安全技术问题一直大伤脑筋,因此在各方压力下终止了航天飞机的历史,但是此类事情会不会在以后发生，谁也无法保证,在遇到这类航天问题时,解决方法也许只能让航天员出仓维修,但是多次的维修会消耗航天员大量的能量,因此NASA便想设计一种食品方案,让体积和承重有限的条件下多装载一些高卡路里的食物.
题目描述
航天飞机的体积有限,当然如果载过重的物品,燃料会浪费很多钱,
每件食品都有各自的体积、质量以及所含卡路里,在告诉你体积
和质量的最大值的情况下,请输出能达到的食品方案所含卡路里
的最大值,当然每个食品只能使用一次.
输入输出格式
输入格式：
第一行 两个数 体积最大值(<400)和质量最大值(<400)
第二行 一个数 食品总数N(<50).
第三行－第3+N行
每行三个数 体积(<400) 质量(<400) 所含卡路里(<500)
输出格式：
一个数 所能达到的最大卡路里(int范围内)

信息学奥赛一本通_潜水员

【题目描述】
潜水员为了潜水要使用特殊的装备。他有一个带2种气体的气缸：一个为氧气，一个为氮气。让潜水员下潜的深度需要各种的数量的氧和氮。潜水员有一定数量的气缸。每个气缸都有重量和气体容量。潜水员为了完成他的工作需要特定数量的氧和氮。他完成工作所需气缸的总重的最低限度的是多少？
例如：潜水员有5个气缸。每行三个数字为：氧，氮的（升）量和气缸的重量：
3 36 120
10 25 129
5 50 250
1 45 130
4 20 119
如果潜水员需要5升的氧和60升的氮则总重最小为249（1，2或者4，5号气缸）。
你的任务就是计算潜水员为了完成他的工作需要的气缸的重量的最低值。
【输入】
第一行有2整数m，n（1≤m≤21，1≤n≤79）。它们表示氧，氮各自需要的量。
第二行为整数k（1≤n≤1000）表示气缸的个数。
此后的k行，每行包括ai，bi，ci（1≤ai≤21，1≤bi≤79，1≤ci≤800）3
整数。这些各自是：第i个气缸里的氧和氮的容量及汽缸重量。
【输出】
仅一行包含一个整数，为潜水员完成工作所需的气缸的重量总和的最低值。
题解（关于填表法和刷表法）

分组背包

分组背包特殊就特殊在，它对物品分组，且每组物品里面还只能选一个
但是其核心还是01背包，毕竟方程都没有变

代码实现

伪代码见下：

for i枚举每一类物品t
	for j倒序枚举体积v
		for k枚举当前这一类物品i的所有子物品
			//设k`为i中一个子物品
			f[j]=max(f[j],f[j-V[k`]]+W[k`])
printf("%d\n",f[V]);

注意，枚举体积V这层循环一定要放在枚举子物品的外面，否则就会出现同一类物品在某个状态内被用了多个的情况

练习

信息学奥赛一本通_分组背包

【题目描述】
一个旅行者有一个最多能装V公斤的背包，现在有n件物品，它们的重量分别是W1，W2，…,Wn
，它们的价值分别为C1,C2,…,Cn。这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
【输入】
第一行：三个整数，V(背包容量，V≤200)，N(物品数量，N≤30)和T(最大组号，T≤10)；
第2…N+1行：每行三个整数Wi,Ci,P，表示每个物品的重量，价值，所属组号。
【输出】
仅一行，一个数，表示最大总价值。

luoguP1757_通天之分组背包

P1757 通天之分组背包
题目背景
直达通天路·小A历险记第二篇
题目描述
自01背包问世之后，小A对此深感兴趣。一天，小A去远游，却发现他的背包不同于01背包，他的物品大致可分为k组，每组中的物品相互冲突，现在，他想知道最大的利用价值是多少。
输入输出格式
输入格式：
两个数m,n，表示一共有n件物品，总重量为m
接下来n行，每行3个数ai,bi,ci，表示物品的重量，利用价值，所属组数
输出格式：
一个数，最大的利用价值

依赖背包

这个。。。看看树形DP就好

---

（本文现在给的例题比较水，后面会追加比较有难度的例题，19/7/15）

---

update2019.7.16——关于背包九讲中的泛化物品和求第k优解

背包九讲原文GitHub下载
拜读了一下崔大牛的背包九讲，发现其中两个比较有趣的东西：

1.泛化物品

考虑这样一种物品，它并没有固定的费用和价值，而是它的价值随着你分配给它的费用而变化。这就是泛化物品的概念。
更严格的定义之。在背包容量为V的背包问题中，泛化物品是一个定义域为0: : : V中的整数的函数h，当分配给它的费用为v时，能得到的价值就是h(v)。
这个定义有一点点抽象，另一种理解是一个泛化物品就是一个数组h[0: : : V]，给它费用v，可得到价值h[v]。 ——背包九讲

概念还是很好理解的，用函数来阐明定义使得定义更加明确
但是这又有什么用呢？
个人感觉这是作者的一个思考模式，因为通过探究，可以发现几乎所有的常见的背包问题都可以转化为一个泛化物品，而求解一个泛化物品一般考虑将其拆成好几个泛化物品来解决，作者通过引入这个概念建立起了一个系统化的思考模式

2.求背包问题的第K优解

比如，01背包问题，让你求第2大的收益这一类的问题
作者在文中提到了一个概念，将状态看成有序队列，以便于保存所有的状态
具体的做法就是：（01背包）在方程式上加一维：$f[i][j][k]$f[i][j][k]是前i个物品，体积为j的第k优解，这样子的话，显然f[i][j]这个一维数组里面的值是单调递减的（$f[i][j][1]&gt;f[i][j][2]....$f[i][j][1]>f[i][j][2]....），这就像一个有序队列一样
再看转移方程：$f[i][j][k]=max(f[i-1][j][k],f[i-1][j-V[i]][k]+W[i])$f[i][j][k]=max(f[i−1][j][k],f[i−1][j−V[i]][k]+W[i])，当我们在枚举k的时候，就相当于把两个有序队列$（f[i-1][j],f[i-1][j-V[i]]+W[i]）$（f[i−1][j],f[i−1][j−V[i]]+W[i]）在进行合并：将较大的值放入新的队列中，小的值就删去，这样操作后队列$f[i][j]$f[i][j]里面的数据个数和单调性都不变
通过这种方法维护出来的数组保存了maxk内所有的决策

一些例题

NOIP2006——金明的预算方案

题解

P1776 宝物筛选_NOI导刊2010提高（02）

[题目描述]
终于，**了千年的难题。小FF找到了王室的宝物室，里面堆满了无数价值连城的宝物……这下小FF可发财了，嘎嘎。但是这里的宝物实在是太多了，小FF的采集车似乎装不下那么多宝物。看来小FF只能含泪舍弃其中的一部分宝物了……小FF对洞穴里的宝物进行了整理，他发现每样宝物都有一件或者多件。他粗略估算了下每样宝物的价值，之后开始了宝物筛选工作：小FF有一个最大载重为W的采集车，洞穴里总共有n种宝物，每种宝物的价值为v[i]，重量为w[i]，每种宝物有m[i]件。小FF希望在采集车不超载的前提下，选择一些宝物装进采集车，使得它们的价值和最大。
[输入格式]
第一行为一个整数N和w，分别表示宝物种数和采集车的最大载重。
接下来n行每行三个整数，其中第i行第一个数表示第i类品价值，第二个整数表示一件该类物品的重量，第三个整数为该类物品数量。
[输出格式]
输出仅一个整数ans，表示在采集车不超载的情况下收集的宝物的最大价值。

多重背包：

#include<bits/stdc++.h>
using namespace std;
#define loop(i,start,end) for(register int i=start;i<=end;++i)
#define anti_loop(i,start,end) for(register int i=start;i>=end;--i)
#define clean(arry,num) memset(arry,num,sizeof(arry))
#define ll long long
template<typename T>void read(T &x){
	x=0;char r=getchar();T neg=1;
	while(r>'9'||r<'0'){if(r=='-')neg=-1;r=getchar();}
	while(r>='0'&&r<='9'){x=(x<<1)+(x<<3)+r-'0';r=getchar();}
	x*=neg;
}

int n,v;
const int maxn=1e5+10,maxv=4e4+10,maxnl=1e5+10;
int W[maxnl];
int V[maxnl];
int f[maxv];
int nl;
inline void chaifen(){
	nl=0;
	loop(i,1,n){
		int _w=0,_v=0,_p=0,t=1;
		read(_w);
		read(_v);
		read(_p);
		while(_p>=t){
			W[++nl]=_w*t;
			V[nl]=_v*t;
			_p-=t;
			t*=2;
		}
		W[++nl]=_w*_p;
		V[nl]=_v*_p;
	}
}

int main(){
	#ifndef ONLINE_JUDGE
	freopen("datain.txt","r",stdin);
	#endif
	
	clean(W,0);
	clean(V,0);
	clean(f,0);
	
	read(n),read(v);
	chaifen();
	
	loop(i,1,nl){
		anti_loop(j,v,V[i]){
			f[j]=max(f[j],f[j-V[i]]+W[i]);
		}
	}
	printf("%d\n",f[v]);
	return 0;
}

选课

[题目描述]
在大学里每个学生，为了达到一定的学分，必须从很多课程里选择一些课程来学习，在课程里有些课程必须在某些课程之前学习，如高等数学总是在其它课程之前学习。现在有N门功课，每门课有个学分，每门课有一门或没有直接先修课（若课程a是课程b的先修课即只有学完了课程a，才能学习课程b）。一个学生要从这些课程里选择M门课程学习，问他能获得的最大学分是多少？
[输入格式]
第一行有两个整数N,M用空格隔开。(1<=N<=300,1<=M<=300)
接下来的N行,第I+1行包含两个整数ki和si, ki表示第I门课的直接先修课，si表示第I门课的学分。若ki=0表示没有直接先修课（1<=ki<=N, 1<=si<=20）。
[输出格式]
只有一行，选M门课程的最大得分。

依赖背包：（多个01背包）

#include<bits/stdc++.h>
using namespace std;
#define loop(i,start,end) for(int i=start;i<=end;i++)
#define anti_loop(i,start,end) for(int i=start;i>=end;i--)
#define clean(arry,num); memset(arry,num,sizeof(arry));
#define min(a,b) (a>b)?b:a
#define max(a,b) (a>b)?a:b
const int maxn=320;int cnt=0;
class treeDP
{
	public:
		int head[maxn];
		int a[maxn];
		struct node
		{
			int e;
			int nxt;
		}edge[maxn<<1];
		int n,m;
		int dp[maxn][maxn];
		void mymain();
	private:
		inline void addl(int u,int v);
		inline int read();
		void datasetting();
		int calc(int u,int fa);
		
}DP;
int treeDP::calc(int u,int fa)
{
	dp[u][0]=0;dp[u][1]=a[u];
	int size=1;
	for(int i=head[u];~i;i=edge[i].nxt)
	{
		int son=edge[i].e;
		if(son==fa)continue;
		int s=calc(son,u);
		size+=s;
		for(int j=size;j>0;j--)
		{
			for (int k=0;k<j;k++)
			{
				if(k>s)continue;
				dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[son][k]);
			}
		}
	}
	return size;
}
inline int treeDP::read()
{
	int ans=0;char r=getchar();
	while(r>'9'||r<'0')r=getchar();
	while(r<='9'&&r>='0')
	{
		ans=ans*10+r-'0';
		r=getchar();
	}
	return ans;
}
inline void treeDP::addl(int u,int v)
{
	edge[cnt].e=v;
	edge[cnt].nxt=head[u];
	head[u]=cnt++;
}
void treeDP::datasetting()
{
	clean(head,-1);
	n=read();m=read();m++;a[0]=0;
	int fa;
	loop(i,1,n)
	{
		fa=read();
		addl(i,fa);
		addl(fa,i);	
		a[i]=read();
	}
}
void treeDP::mymain()
{
	datasetting();
	calc(0,-1);
	printf("%d",dp[0][m]);
}
int main()
{
	DP.mymain();
	return 0;
}