2023年7月31日发(作者：)

动态规划初步之背包问题（参考背包九讲+例题+详细分析+补充）1 01背包问题1.1 题⽬有N件物品和⼀个容量为V 的背包。放⼊第i件物品耗费的空间是Ci，得到 的价值是Wi。求解将哪些物品装⼊背包可使价值总和最⼤。1.2 基本思路这是最基础的背包问题，特点是：每种物品仅有⼀件，可以选择放或不 放。 ⽤⼦问题定义状态：即F[i,v]表⽰前i件物品恰放⼊⼀个容量为v的背包可以 获得的最⼤价值。则其状态转移⽅程便是：F[i,v] = max{F[i−1,v],F[i−1,v−Ci] + Wi}

这个⽅程⾮常重要，基本上所有跟背包相关的问题的⽅程都是由它衍⽣ 出来的。所以有必要将它详细解释⼀下：“将前i件物品放⼊容量为v的背包中”这个⼦问题，若只考虑第i件物品的策略（放或不放），那么就可以转化 为⼀个只和前i−1件物品相关的问题。如果不放第i件物品，那么问题就转化 为“前i−1件物品放⼊容量为v的背包中”，价值为F[i−1,v]；如果放第i件物 品，那么问题就转化为“前i−1件物品放⼊剩下的容量为v −Ci的背包中”， 此时能获得的最⼤价值就是F[i−1,v −Ci]再加上通过放⼊第i件物品获得的价 值Wi。 伪代码如下：

F[0,0..V ] = 0

for i = 1 to N

for v = Ci to V

F[i,v] = max{F[i−1,v],F[i−1,v−Ci] + Wi}例：在使⽤动态规划算法求解0-1背包问题时，使⽤⼆维数组m[i][j]存储背包剩余容量为j，可选物品为i、i+1、……、n时0-1背包问题的最优值。绘制价值数组v = {8, 10, 6, 3, 7, 2}，重量数组w = {4, 6, 2, 2, 5, 1}，背包容量C = 12时对应的m[i][j]数组。6668488899958889924242424第⼀⾏和第⼀列为序号，其数值为0)如m[2][6],在⾯对第⼆件物品，背包容量为6时我们可以选择不拿，那么获得价值仅为第⼀件物品的价值8，如果拿，就要把第⼀件物品拿出来，放第⼆件物品，价值10，那我们当然是选择拿。m[2][6]=m[1][0]+10=0+10=10;依次类推，得到m[6][12]就是考虑所有物品，背包容量为C时的最⼤价值。#include #include using namespace std;

const int N=15;

int main(){ int v[N]={0,8,10,6,3,7,2}; int w[N]={0,4,6,2,2,5,1};

int m[N][N]; int n=6,c=12; memset(m,0,sizeof(m)); for(int i=1;i<=n;i++) { for(int j=1;j<=c;j++) { if(j>=w[i]) m[i][j]=max(m[i-1][j],m[i-1][j-w[i]]+v[i]);

else m[i][j]=m[i-1][j]; } }

for(int i=1;i<=n;i++) { for(int j=1;j<=c;j++) { cout<

return 0;}1.3 优化空间复杂度以上⽅法的时间和空间复杂度均为O(V N)，其中时间复杂度应该已经不能 再优化了，但空间复杂度却可以优化到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−Ci]两个⼦问题递推⽽来，能否保证在推F[i,v]时（也 即在第i次主循环中推F[v]时）能够取⽤F[i−1,v]和F[i−1,v −Ci]的值呢？事 实上，这要求在每次主循环中我们以v = V..0的递减顺序计算F[v]，这样才能保 证推F[v]时F[v−Ci]保存的是状态F[i−1,v−Ci]的值。伪代码如下：F[0..V ] = 0

for i = 1 to N

for v = V to Ci

F[v] = max{F[v],F[v−Ci] + Wi}其中的F[v] = max{F[v],F[v −Ci] + Wi}⼀句，恰就对应于我们原来的转移⽅ 程，因为现在的F[v−Ci]就相当于原来的F[i−1,v−Ci]。如果将v的循环顺序 从上⾯的逆序改成顺序的话，那么则成了F[i,v]由F[i,v−Ci]推导得到，与本题 意不符。 事实上，使⽤⼀维数组解01背包的程序在后⾯会被多次⽤到，所以这⾥抽象 出⼀个处理⼀件01背包中的物品过程，以后的代码中直接调⽤不加说明。 有了这个过程以后，01背包问题的伪代码就可以这样写：for i = 1 to N

for v = V to C

F[v] = max(F[v],f[v−C] + W)1.4 初始化的细节问题我们看到的求最优解的背包问题题⽬中，事实上有两种不太相同的问法。 有的题⽬要求“恰好装满背包”时的最优解，有的题⽬则并没有要求必须把背 包装满。⼀种区别这两种问法的实现⽅法是在初始化的时候有所不同。如果是第⼀种问法，要求恰好装满背包，那么在初始化时除了F[0]为0，其 它F[1..V ]均设为−∞，这样就可以保证最终得到的F[V ]是⼀种恰好装满背包的 最优解。 如果并没有要求必须把背包装满，⽽是只希望价格尽量⼤，初始化时应该 将F[0..V ]全部设为0。 这是为什么呢？可以这样理解：初始化的F数组事实上就是在没有任何物 品可以放⼊背包时的合法状态。如果要求背包恰好装满，那么此时只有容量 为0的背包可以在什么也不装且价值为0的情况下被“恰好装满”，其它容量的 背包均没有合法的解，属于未定义的状态，应该被赋值为-∞了。如果背包并⾮ 必须被装满，那么任何容量的背包都有⼀个合法解“什么都不装”，这个解的 价值为0，所以初始时状态的值也就全部为0了。 这个⼩技巧完全可以推⼴到其它类型的背包问题，后⾯也就不再对进⾏状 态转移之前的初始化进⾏讲解。练习题hdu2602#include#includeint max(int a,int b){ return a>b?a:b;}int main(){ int T,N,V; int i,j; int bag[1010],v[1010],w[1010]; scanf("%d",&T); while(T--) { memset(bag,0,sizeof(bag));//把背包各个状态是的价值设为0 scanf("%d%d",&N,&V); for(i=0;i=w[i];j--){ //j状态的背包（计算重量为j是的最⼤价值） bag[j]=max(bag[j],bag[j-w[i]]+v[i]); } printf("%dn",bag[V]); } return 0;}hdu2546#include#include#includeusing namespace std;int main(){ int N,V,m; int i,j; int bag[1010],v[1010]; while(~scanf("%d",&N),N) { memset(bag,0,sizeof(bag)); for(i=0;i

scanf("%d",&m);//把卡余额m看做背包容量 //饭菜的价格即代表他的价值，也代表他的重量 V=m-5;//我们的⽬的是把卡余额尽量刷到5元 if(m<5){ printf("%dn",m); continue; } for(i=0;i=v[i];j--){ bag[j]=max(bag[j],bag[j-v[i]]+v[i]); } printf("%dn",m-v[N-1]-bag[V]);//减掉最贵的菜，和规划好的最⼤消费 } return 0;}到这⼀步，可以确定的是可能获得的最⼤价值，但是我们并不清楚具体选择哪⼏样物品能获得最⼤价值。另起⼀个 x[ ] 数组，x[i]=0表⽰不拿，x[i]=1表⽰拿。m[n][c]为最优值，如果m[n][c]=m[n-1][c] ,说明有没有第n件物品都⼀样，则x[n]=0 ; 否则 x[n]=1。当x[n]=0时，由x[n-1][c]继续构造最优解；当x[n]=1时，则由x[n-1][c-w[i]]继续构造最优解。以此类推，可构造出所有的最优解。void traceback(){ for(int i=n;i>1;i--) { if(m[i][c]==m[i-1][c]) x[i]=0; else { x[i]=1; c-=w[i]; } } x[1]=(m[1][c]>0)?1:0;}例：

某⼯⼚预计明年有A、B、C、D四个新建项⽬，每个项⽬的投资额Wk及其投资后的收益Vk如下表所⽰，投资总额为30万元，如何选择项⽬才能使总收益最⼤？ ProjectABCDWk1510128Vk12895结合前⾯两段代码#include #include using namespace std;

const int N=150;

int v[N]={0,12,8,9,5};int w[N]={0,15,10,12,8};int x[N];int m[N][N];int c=30;int n=4;void traceback(){ for(int i=n;i>1;i--) { if(m[i][c]==m[i-1][c]) x[i]=0; else { x[i]=1; c-=w[i]; } } x[1]=(m[1][c]>0)?1:0;}

int main(){

memset(m,0,sizeof(m)); for(int i=1;i<=n;i++) { for(int j=1;j<=c;j++) { if(j>=w[i]) m[i][j]=max(m[i-1][j],m[i-1][j-w[i]]+v[i]);

else m[i][j]=m[i-1][j]; } }/* for(int i=1;i<=6;i++) { for(int j=1;j<=c;j++) { cout<

for i = 1 to N

for v = Ci to V

F[v] = max(F[v],F[v−Ci] + Wi)你会发现，这个伪代码与01背包问题的伪代码只有v的循环次序不同⽽已。 为什么这个算法就可⾏呢？⾸先想想为什么01背包中要按照v递减的次序来 循环。让v递减是为了保证第i次循环中的状态F[i,v]是由状态F[i−1,v −Ci]递 推⽽来。换句话说，这正是为了保证每件物品只选⼀次，保证在考虑“选⼊ 第i件物品”这件策略时，依据的是⼀个绝⽆已经选⼊第i件物品的⼦结果F[i− 1,v −Ci]。⽽现在完全背包的特点恰是每种物品可选⽆限件，所以在考虑“加 选⼀件第i种物品”这种策略时，却正需要⼀个可能已选⼊第i种物品的⼦结 果F[i,v−Ci]，所以就可以并且必须采⽤v递增的顺序循环。这就是这个简单的 程序为何成⽴的道理。 值得⼀提的是，上⾯的伪代码中两层for循环的次序可以颠倒。这个结论有 可能会带来算法时间常数上的优化。 这个算法也可以由另外的思路得出。例如，将基本思路中求解F[i,v−Ci]的 状态转移⽅程显式地写出来，代⼊原⽅程中，会发现该⽅程可以等价地变形成 这种形式：F[i,v] = max(F[i−1,v],F[i,v−Ci] + Wi)

将这个⽅程⽤⼀维数组实现，便得到了上⾯的伪代码。2.6 ⼩结完全背包问题也是⼀个相当基础的背包问题，它有两个状态转移⽅程。但是归根结底都要转化成01背包，要牢记不同点。注意：和01背包仅有⼀点区别，就是循环顺序。但是动态规划出来的结果是截然不同的！ 先回忆⼀下01背包为什么要到这循环，因为每⼀个物品在装进去的时候，都要⽤到前⼀个状态的数据来计算当前物品要不要加⼊。简单说，就是由前⾯物品装好的状态推出当前物品装⼊的状态。 ⽽内循环为正序时，先更新状态，再⽤更新了的状态继续更新当前状态，就产⽣了⼀个现象：在不超背包容量的状态下，我可以⼀直⽤当前物品不断更新背包状态，即不断往背包⾥填同⼀个物品。打个⽐⽅，我想在正在装⼀个重m的物品，进⼊内循环，我先把f [m] 这个状态更新了，想在f [m]就是装⼊了m后的最⼤价值，继续更新f [m+1]的状态，我会⽤到 f [j]=max( f [j], f [j-v[i]]+v[i]); 这个语句，也就是会调⽤到更⼩重量时的状态，⽽我恰好在这之前更新过了，那不就是我可以第⼆次把物品m装进背包吗。以此类推，我往后更新状态过程中，我可以⽆限的把同⼀个物品 i 往⾥装。例题3：题意：某⼈有个存钱罐（存硬币），空着的时候重E，存满钱是重F。现在他把罐⼦装满钱了，给出硬币种类和重量，计算存钱罐最少能存多少钱。思路：完全背包。每种硬币可以⽆限放。但是这⾥不是求最⼤价值，⽽是求最⼩价值，所以我们先假设所有状态为正⽆穷，然后不断更新dp，以求得最⼩价值。这样在动态规划时需要注意⼀点，状态0始终未0，即f [ 0 ] =0恒成⽴#include#includeusing namespace std;const int INF=0x6fffffff;int f[10010];int main(){ int T,E,F,M,N; int p,w; //价值和重量 scanf("%d",&T); while(T--) { for(int i=1;i<=10002;i++)f[i]=INF; f[0]=0;//这⼀步很重要，给动态规划⼀个开头 scanf("%d%d%d",&E,&F,&N); M=F-E; //最⼤钱数M for(int i=0;i 0的最⼤整数。例 如，如果Mi为13，则相应的k = 3，这种最多取13件的物品应被分成系数分别 为1,2,4,6的四件物品。 分成的这⼏件物品的系数和为Mi，表明不可能取多于Mi件的第i种物品。另 外这种⽅法也能保证对于0...Mi间的每⼀个整数，均可以⽤若⼲个系数的和表 ⽰。这⾥算法正确性的证明可以分0...2k−1和2k ...Mi两段来分别讨论得出， 希望读者⾃⼰思考尝试⼀下。 这样就将第i种物品分成了O(logMi)种物品，将原问题转化为了复杂度 为O(V ΣlogMi)的01背包问题，是很⼤的改进。 下⾯给出O(logM)时间处理⼀件多重背包中物品的过程：

def MultiplePack(F,C,W,M)

if C ·M ≥ V

CompletePack(F,C,W)

return k := 1

while k < M

ZeroOnePack(kC,kW) M := M −k k := 2k

ZeroOnePack(C ·M,W ·M)

3.4 O(VN)的算法多重背包问题同样有O(V N)复杂度的算法。这个算法基于基本算法的状态 转移⽅程，但应⽤单调队列的⽅法使每个状态的值可以以均摊O(1)的时间求 解。#includetypedef long long ll;templateT max(T a,T b){ return a>b?a:b;}ll f[60000];ll w[2002000];ll p[2002000];int main(){ int n,W; scanf("%d%d",&n,&W); int k=0; for(int i=0;i0) { if(c1>t) { w[k]=t*w1; p[k]=t*p1; } else { w[k]=c1*w1; p[k]=c1*p1; } c1=c1-t; t=t*2; k++; } } for(int i=0;i=w[i];j--) { f[j]=max(f[j],f[j-w[i]]+p[i]); } printf("%lldn",f[W]); return 0;}

例题： //HDU 2191 多重背包

#includeint val[110],wei[110],count[110],dp[110];//价格，重量，袋数。动态背包

int max(int a,int b){ return a>b?a:b;}int main(){ int T; scanf("%d",&T); while(T--) { int n,m;// 钱数，种类

scanf("%d%d",&n,&m); for(int i=0;i

for(int i=0;i

for(int k=1;k<=count[i];k++) //⼤⽶ i 放⼊的次数

for(int j=n;j>=val[i];j--) // 动态规划

dp[j]=max(dp[j],dp[j-val[i]]+wei[i]); printf("%dn",dp[n]); //数组dp存的是重量

} return 0;}5 ⼆维费⽤的背包问题5.1 问题⼆维费⽤的背包问题是指：对于每件物品，具有两种不同的空间耗费，选 择这件物品必须同时付出这两种代价。对于每种代价都有⼀个可付出的最⼤值 （背包容量）。问怎样选择物品可以得到最⼤的价值。 设这两种代价分别为代价⼀和代价⼆，第i件物品所需的两种代价分别为Ci和Di。两种代价可付出的最⼤值（两种背包容量）分别为V 和U。物品的 价值为Wi。5.2 算法费⽤加了⼀维，只需状态也加⼀维即可。设F[i,v,u]表⽰前i件物品付出两 种代价分别为v和u时可获得的最⼤价值。状态转移⽅程就是：F[i,v,u] = max{F[i−1,v,u],F[i−1,v−Ci,u−Di] + Wi} 如前述优化空间复杂度的⽅法，可以只使⽤⼆维的数组：当每件物品只可 以取⼀次时变量v和u采⽤逆序的循环，当物品有如完全背包问题时采⽤顺序的 循环，当物品有如多重背包问题时拆分物品。 这⾥就不再给出伪代码了，相信有了前⾯的基础，读者应该能够⾃⼰实现 出这个问题的程序。5.3 物品总个数的限制有时，“⼆维费⽤”的条件是以这样⼀种隐含的⽅式给出的：最多只能 取U件物品。这事实上相当于每件物品多了⼀种“件数”的费⽤，每个物品的 件数费⽤均为1，可以付出的最⼤件数费⽤为U。换句话说，设F[v,u]表⽰付 出费⽤v、最多选u件时可得到的最⼤价值，则根据物品的类型（01、完全、多 重）⽤不同的⽅法循环更新，最后在U]范围内寻找答案。6 分组的背包问题6.1 问题有N件物品和⼀个容量为V 的背包。第i件物品的费⽤是Ci，价值是Wi。这 些物品被划分为K组，每组中的物品互相冲突，最多选⼀件。求解将哪些物品 装⼊背包可使这些物品的费⽤总和不超过背包容量，且价值总和最⼤。6.2 算法这个问题变成了每组物品有若⼲种策略：是选择本组的某⼀件，还是⼀件 都不选。也就是说设F[k,v]表⽰前k组物品花费费⽤v能取得的最⼤权值，则 有： F[k,v] = max{F[k−1,v],F[k−1,v−Ci] + Wi |item i ∈ group k} 使⽤⼀维数组的伪代码如下：

for k = 1 to K

for v = V to 0

for item i in group k

F[v] = max{F[v],F[v−Ci] + Wi}7 有依赖的背包问题7.1 简化的问题这种背包问题的物品间存在某种“依赖”的关系。也就是说，物品i依赖于 物品j，表⽰若选物品i，则必须选物品j。为了简化起见，我们先设没有某个物 品既依赖于别的物品，⼜被别的物品所依赖；另外，没有某件物品同时依赖多 件物品。7.2 算法这个问题由NOIP2006题⽬中⾦明的预算⽅案⼀题扩展⽽来。遵从该题的提 法，将不依赖于别的物品的物品称为“主件”，依赖于某主件的物品称为“附 件”。由这个问题的简化条件可知所有的物品由若⼲主件和依赖于每个主件的 ⼀个附件集合组成。 按照背包问题的⼀般思路，仅考虑⼀个主件和它的附件集合。可是，可⽤ 的策略⾮常多，包括：⼀个也不选，仅选择主件，选择主件后再选择⼀个附 件，选择主件后再选择两个附件……⽆法⽤状态转移⽅程来表⽰如此多的策 略。事实上，设有n个附件，则策略有2n + 1个，为指数级。考虑到所有这些策略都是互斥的（也就是说，你只能选择⼀种策略），所 以⼀个主件和它的附件集合实际上对应于6中的⼀个物品组，每个选择了主件⼜ 选择了若⼲个附件的策略对应于这个物品组中的⼀个物品，其费⽤和价值都是 这个策略中的物品的值的和。但仅仅是这⼀步转化并不能给出⼀个好的算法， 因为物品组中的物品还是像原问题的策略⼀样多。 再考虑对每组内的物品应⽤2.3中的优化。我们可以想到，对于第k个物品组 中的物品，所有费⽤相同的物品只留⼀个价值最⼤的，不影响结果。所以，可 以对主件k的“附件集合”先进⾏⼀次01背包，得到费⽤依次为0...V − Ck所 有这些值时相应的最⼤价值V −Ck]。那么，这个主件及它的附件集合 相当于V −Ck + 1个物品的物品组，其中费⽤为v的物品的价值为Fk[v −Ck] + Wk，v的取值范围是Ck ≤ v ≤ V 。 也就是说，原来指数级的策略中，有很多策略都是冗余的，通过⼀次01背包 后，将主件k及其附件转化为V −Ck + 1个物品的物品组，就可以直接应⽤6的 算法解决问题了。7.3 较⼀般的问题更⼀般的问题是：依赖关系以图论中“森林”1的形式给出。也就是说，主 件的附件仍然可以具有⾃⼰的附件集合。限制只是每个物品最多只依赖于⼀个 物品（只有⼀个主件）且不出现循环依赖。 解决这个问题仍然可以⽤将每个主件及其附件集合转化为物品组的⽅式。 唯⼀不同的是，由于附件可能还有附件，就不能将每个附件都看作⼀个⼀般 的01背包中的物品了。若这个附件也有附件集合，则它必定要被先转化为物品 组，然后⽤分组的背包问题解出主件及其附件集合所对应的附件组中各个费⽤ 的附件所对应的价值。 事实上，这是⼀种树形动态规划，其特点是，在⽤动态规划求每个⽗节点 的属性之前，需要对它的各个⼉⼦的属性进⾏⼀次动态规划式的求值。这已经 触及到了“泛化物品”的思想。看完8后，你会发现这个“依赖关系树”每⼀个 ⼦树都等价于⼀件泛化物品，求某节点为根的⼦树对应的泛化物品相当于求其 所有⼉⼦的对应的泛化物品之和

附加：01背包第k个最优解 思想与01背包相同，不过在动态规划过程中，不可以把前⼀个状态的最优解扔掉，⽽要保存下来。在01背包中，状态数组是 f [ v ] ，表⽰容积为v时的最优决策。⽽现在，我不仅要知道最优决策，我还想知道稍微差⼀点的决策，即第2决策、第3决策....排个名。f [ v ] 我们可以看做是 f [ v ] [ 1 ] 这样的⼆维数组，他的第⼆维只有⼀个元素，也就是最优决策。现在我们增⼤第⼆维，⽐如 f [ v ] [ 3 ] ，意思是，不仅保留了最优解，次解也保留下来了。也可以理解为，第⼆维是⼀个集合，集合⾥就存了所有可能的决策，并按⼤⼩有序，排在第⼀的就是最优解。现在问题是 第k个最优决策是多少。 在01背包⾥，我们只保留了最优解，⽽把不是最优解的解直接舍弃了，即

f[j]=max(f[j],f[j-w[i]]+v[i])这时候，较⼩的那个解直接舍弃了，没保留下来。现在我们要做的就是，借助数组把所有的解都保留下来。核⼼代码： int i,j,t; for(i=0;i=vol[i];j--) //对每个状态进⾏更新

{ for(t=1;t<=k;t++) { //把所有可能的解都存起来 a[t]=f[j][t]; b[t]=f[j-vol[i]][t]+val[i]; } int m,x,y; m=x=y=1; a[k+1]=b[k+1]=-1; //下⾯的循环相当于求a和b并集，也就是所有的可能解

while(m<=k && (a[x]!=-1 || b[y]!=-1)) { if(a[x]>b[y]) f[j][m]=a[x++]; else

f[j][m]=b[y++];

if(f[j][m]!=f[j][m-1]) m++; } }例题：板⼦题）代码：#include

#includeint f[1010][33];//第⼀维和普通01背包⼀样。第⼆维存多个最优解int val[110],vol[110];//价值和体积int a[33],b[33];//⽤于暂时存储多组最优解

int n,v,k;int i,j,t,T;int main(){ scanf("%d",&T); while(T--) { scanf("%d%d%d",&n,&v,&k); for(i=0;i

for(i=0;i=vol[i];j--) //对每个状态进⾏更新

{ for(t=1;t<=k;t++) { //把所有可能的解都存起来 a[t]=f[j][t]; b[t]=f[j-vol[i]][t]+val[i]; } int m,x,y; m=x=y=1; a[k+1]=b[k+1]=-1; //下⾯的循环相当于求a和b并集，也就是所有的可能解

while(m<=k && (a[x]!=-1 || b[y]!=-1)) { if(a[x]>b[y]) f[j][m]=a[x++]; else

f[j][m]=b[y++];

if(f[j][m]!=f[j][m-1]) m++; } } printf("%dn",f[v][k]); } return 0; }

2023年7月31日发(作者：)

动态规划初步之背包问题（参考背包九讲+例题+详细分析+补充）1 01背包问题1.1 题⽬有N件物品和⼀个容量为V 的背包。放⼊第i件物品耗费的空间是Ci，得到 的价值是Wi。求解将哪些物品装⼊背包可使价值总和最⼤。1.2 基本思路这是最基础的背包问题，特点是：每种物品仅有⼀件，可以选择放或不 放。 ⽤⼦问题定义状态：即F[i,v]表⽰前i件物品恰放⼊⼀个容量为v的背包可以 获得的最⼤价值。则其状态转移⽅程便是：F[i,v] = max{F[i−1,v],F[i−1,v−Ci] + Wi}

这个⽅程⾮常重要，基本上所有跟背包相关的问题的⽅程都是由它衍⽣ 出来的。所以有必要将它详细解释⼀下：“将前i件物品放⼊容量为v的背包中”这个⼦问题，若只考虑第i件物品的策略（放或不放），那么就可以转化 为⼀个只和前i−1件物品相关的问题。如果不放第i件物品，那么问题就转化 为“前i−1件物品放⼊容量为v的背包中”，价值为F[i−1,v]；如果放第i件物 品，那么问题就转化为“前i−1件物品放⼊剩下的容量为v −Ci的背包中”， 此时能获得的最⼤价值就是F[i−1,v −Ci]再加上通过放⼊第i件物品获得的价 值Wi。 伪代码如下：

F[0,0..V ] = 0

for i = 1 to N

for v = Ci to V

F[i,v] = max{F[i−1,v],F[i−1,v−Ci] + Wi}例：在使⽤动态规划算法求解0-1背包问题时，使⽤⼆维数组m[i][j]存储背包剩余容量为j，可选物品为i、i+1、……、n时0-1背包问题的最优值。绘制价值数组v = {8, 10, 6, 3, 7, 2}，重量数组w = {4, 6, 2, 2, 5, 1}，背包容量C = 12时对应的m[i][j]数组。6668488899958889924242424第⼀⾏和第⼀列为序号，其数值为0)如m[2][6],在⾯对第⼆件物品，背包容量为6时我们可以选择不拿，那么获得价值仅为第⼀件物品的价值8，如果拿，就要把第⼀件物品拿出来，放第⼆件物品，价值10，那我们当然是选择拿。m[2][6]=m[1][0]+10=0+10=10;依次类推，得到m[6][12]就是考虑所有物品，背包容量为C时的最⼤价值。#include #include using namespace std;

const int N=15;

int main(){ int v[N]={0,8,10,6,3,7,2}; int w[N]={0,4,6,2,2,5,1};

int m[N][N]; int n=6,c=12; memset(m,0,sizeof(m)); for(int i=1;i<=n;i++) { for(int j=1;j<=c;j++) { if(j>=w[i]) m[i][j]=max(m[i-1][j],m[i-1][j-w[i]]+v[i]);

else m[i][j]=m[i-1][j]; } }

for(int i=1;i<=n;i++) { for(int j=1;j<=c;j++) { cout<

return 0;}1.3 优化空间复杂度以上⽅法的时间和空间复杂度均为O(V N)，其中时间复杂度应该已经不能 再优化了，但空间复杂度却可以优化到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−Ci]两个⼦问题递推⽽来，能否保证在推F[i,v]时（也 即在第i次主循环中推F[v]时）能够取⽤F[i−1,v]和F[i−1,v −Ci]的值呢？事 实上，这要求在每次主循环中我们以v = V..0的递减顺序计算F[v]，这样才能保 证推F[v]时F[v−Ci]保存的是状态F[i−1,v−Ci]的值。伪代码如下：F[0..V ] = 0

for i = 1 to N

for v = V to Ci

F[v] = max{F[v],F[v−Ci] + Wi}其中的F[v] = max{F[v],F[v −Ci] + Wi}⼀句，恰就对应于我们原来的转移⽅ 程，因为现在的F[v−Ci]就相当于原来的F[i−1,v−Ci]。如果将v的循环顺序 从上⾯的逆序改成顺序的话，那么则成了F[i,v]由F[i,v−Ci]推导得到，与本题 意不符。 事实上，使⽤⼀维数组解01背包的程序在后⾯会被多次⽤到，所以这⾥抽象 出⼀个处理⼀件01背包中的物品过程，以后的代码中直接调⽤不加说明。 有了这个过程以后，01背包问题的伪代码就可以这样写：for i = 1 to N

for v = V to C

F[v] = max(F[v],f[v−C] + W)1.4 初始化的细节问题我们看到的求最优解的背包问题题⽬中，事实上有两种不太相同的问法。 有的题⽬要求“恰好装满背包”时的最优解，有的题⽬则并没有要求必须把背 包装满。⼀种区别这两种问法的实现⽅法是在初始化的时候有所不同。如果是第⼀种问法，要求恰好装满背包，那么在初始化时除了F[0]为0，其 它F[1..V ]均设为−∞，这样就可以保证最终得到的F[V ]是⼀种恰好装满背包的 最优解。 如果并没有要求必须把背包装满，⽽是只希望价格尽量⼤，初始化时应该 将F[0..V ]全部设为0。 这是为什么呢？可以这样理解：初始化的F数组事实上就是在没有任何物 品可以放⼊背包时的合法状态。如果要求背包恰好装满，那么此时只有容量 为0的背包可以在什么也不装且价值为0的情况下被“恰好装满”，其它容量的 背包均没有合法的解，属于未定义的状态，应该被赋值为-∞了。如果背包并⾮ 必须被装满，那么任何容量的背包都有⼀个合法解“什么都不装”，这个解的 价值为0，所以初始时状态的值也就全部为0了。 这个⼩技巧完全可以推⼴到其它类型的背包问题，后⾯也就不再对进⾏状 态转移之前的初始化进⾏讲解。练习题hdu2602#include#includeint max(int a,int b){ return a>b?a:b;}int main(){ int T,N,V; int i,j; int bag[1010],v[1010],w[1010]; scanf("%d",&T); while(T--) { memset(bag,0,sizeof(bag));//把背包各个状态是的价值设为0 scanf("%d%d",&N,&V); for(i=0;i=w[i];j--){ //j状态的背包（计算重量为j是的最⼤价值） bag[j]=max(bag[j],bag[j-w[i]]+v[i]); } printf("%dn",bag[V]); } return 0;}hdu2546#include#include#includeusing namespace std;int main(){ int N,V,m; int i,j; int bag[1010],v[1010]; while(~scanf("%d",&N),N) { memset(bag,0,sizeof(bag)); for(i=0;i

scanf("%d",&m);//把卡余额m看做背包容量 //饭菜的价格即代表他的价值，也代表他的重量 V=m-5;//我们的⽬的是把卡余额尽量刷到5元 if(m<5){ printf("%dn",m); continue; } for(i=0;i=v[i];j--){ bag[j]=max(bag[j],bag[j-v[i]]+v[i]); } printf("%dn",m-v[N-1]-bag[V]);//减掉最贵的菜，和规划好的最⼤消费 } return 0;}到这⼀步，可以确定的是可能获得的最⼤价值，但是我们并不清楚具体选择哪⼏样物品能获得最⼤价值。另起⼀个 x[ ] 数组，x[i]=0表⽰不拿，x[i]=1表⽰拿。m[n][c]为最优值，如果m[n][c]=m[n-1][c] ,说明有没有第n件物品都⼀样，则x[n]=0 ; 否则 x[n]=1。当x[n]=0时，由x[n-1][c]继续构造最优解；当x[n]=1时，则由x[n-1][c-w[i]]继续构造最优解。以此类推，可构造出所有的最优解。void traceback(){ for(int i=n;i>1;i--) { if(m[i][c]==m[i-1][c]) x[i]=0; else { x[i]=1; c-=w[i]; } } x[1]=(m[1][c]>0)?1:0;}例：

某⼯⼚预计明年有A、B、C、D四个新建项⽬，每个项⽬的投资额Wk及其投资后的收益Vk如下表所⽰，投资总额为30万元，如何选择项⽬才能使总收益最⼤？ ProjectABCDWk1510128Vk12895结合前⾯两段代码#include #include using namespace std;

const int N=150;

int v[N]={0,12,8,9,5};int w[N]={0,15,10,12,8};int x[N];int m[N][N];int c=30;int n=4;void traceback(){ for(int i=n;i>1;i--) { if(m[i][c]==m[i-1][c]) x[i]=0; else { x[i]=1; c-=w[i]; } } x[1]=(m[1][c]>0)?1:0;}

int main(){

memset(m,0,sizeof(m)); for(int i=1;i<=n;i++) { for(int j=1;j<=c;j++) { if(j>=w[i]) m[i][j]=max(m[i-1][j],m[i-1][j-w[i]]+v[i]);

else m[i][j]=m[i-1][j]; } }/* for(int i=1;i<=6;i++) { for(int j=1;j<=c;j++) { cout<

for i = 1 to N

for v = Ci to V

F[v] = max(F[v],F[v−Ci] + Wi)你会发现，这个伪代码与01背包问题的伪代码只有v的循环次序不同⽽已。 为什么这个算法就可⾏呢？⾸先想想为什么01背包中要按照v递减的次序来 循环。让v递减是为了保证第i次循环中的状态F[i,v]是由状态F[i−1,v −Ci]递 推⽽来。换句话说，这正是为了保证每件物品只选⼀次，保证在考虑“选⼊ 第i件物品”这件策略时，依据的是⼀个绝⽆已经选⼊第i件物品的⼦结果F[i− 1,v −Ci]。⽽现在完全背包的特点恰是每种物品可选⽆限件，所以在考虑“加 选⼀件第i种物品”这种策略时，却正需要⼀个可能已选⼊第i种物品的⼦结 果F[i,v−Ci]，所以就可以并且必须采⽤v递增的顺序循环。这就是这个简单的 程序为何成⽴的道理。 值得⼀提的是，上⾯的伪代码中两层for循环的次序可以颠倒。这个结论有 可能会带来算法时间常数上的优化。 这个算法也可以由另外的思路得出。例如，将基本思路中求解F[i,v−Ci]的 状态转移⽅程显式地写出来，代⼊原⽅程中，会发现该⽅程可以等价地变形成 这种形式：F[i,v] = max(F[i−1,v],F[i,v−Ci] + Wi)

将这个⽅程⽤⼀维数组实现，便得到了上⾯的伪代码。2.6 ⼩结完全背包问题也是⼀个相当基础的背包问题，它有两个状态转移⽅程。但是归根结底都要转化成01背包，要牢记不同点。注意：和01背包仅有⼀点区别，就是循环顺序。但是动态规划出来的结果是截然不同的！ 先回忆⼀下01背包为什么要到这循环，因为每⼀个物品在装进去的时候，都要⽤到前⼀个状态的数据来计算当前物品要不要加⼊。简单说，就是由前⾯物品装好的状态推出当前物品装⼊的状态。 ⽽内循环为正序时，先更新状态，再⽤更新了的状态继续更新当前状态，就产⽣了⼀个现象：在不超背包容量的状态下，我可以⼀直⽤当前物品不断更新背包状态，即不断往背包⾥填同⼀个物品。打个⽐⽅，我想在正在装⼀个重m的物品，进⼊内循环，我先把f [m] 这个状态更新了，想在f [m]就是装⼊了m后的最⼤价值，继续更新f [m+1]的状态，我会⽤到 f [j]=max( f [j], f [j-v[i]]+v[i]); 这个语句，也就是会调⽤到更⼩重量时的状态，⽽我恰好在这之前更新过了，那不就是我可以第⼆次把物品m装进背包吗。以此类推，我往后更新状态过程中，我可以⽆限的把同⼀个物品 i 往⾥装。例题3：题意：某⼈有个存钱罐（存硬币），空着的时候重E，存满钱是重F。现在他把罐⼦装满钱了，给出硬币种类和重量，计算存钱罐最少能存多少钱。思路：完全背包。每种硬币可以⽆限放。但是这⾥不是求最⼤价值，⽽是求最⼩价值，所以我们先假设所有状态为正⽆穷，然后不断更新dp，以求得最⼩价值。这样在动态规划时需要注意⼀点，状态0始终未0，即f [ 0 ] =0恒成⽴#include#includeusing namespace std;const int INF=0x6fffffff;int f[10010];int main(){ int T,E,F,M,N; int p,w; //价值和重量 scanf("%d",&T); while(T--) { for(int i=1;i<=10002;i++)f[i]=INF; f[0]=0;//这⼀步很重要，给动态规划⼀个开头 scanf("%d%d%d",&E,&F,&N); M=F-E; //最⼤钱数M for(int i=0;i 0的最⼤整数。例 如，如果Mi为13，则相应的k = 3，这种最多取13件的物品应被分成系数分别 为1,2,4,6的四件物品。 分成的这⼏件物品的系数和为Mi，表明不可能取多于Mi件的第i种物品。另 外这种⽅法也能保证对于0...Mi间的每⼀个整数，均可以⽤若⼲个系数的和表 ⽰。这⾥算法正确性的证明可以分0...2k−1和2k ...Mi两段来分别讨论得出， 希望读者⾃⼰思考尝试⼀下。 这样就将第i种物品分成了O(logMi)种物品，将原问题转化为了复杂度 为O(V ΣlogMi)的01背包问题，是很⼤的改进。 下⾯给出O(logM)时间处理⼀件多重背包中物品的过程：

def MultiplePack(F,C,W,M)

if C ·M ≥ V

CompletePack(F,C,W)

return k := 1

while k < M

ZeroOnePack(kC,kW) M := M −k k := 2k

ZeroOnePack(C ·M,W ·M)

3.4 O(VN)的算法多重背包问题同样有O(V N)复杂度的算法。这个算法基于基本算法的状态 转移⽅程，但应⽤单调队列的⽅法使每个状态的值可以以均摊O(1)的时间求 解。#includetypedef long long ll;templateT max(T a,T b){ return a>b?a:b;}ll f[60000];ll w[2002000];ll p[2002000];int main(){ int n,W; scanf("%d%d",&n,&W); int k=0; for(int i=0;i0) { if(c1>t) { w[k]=t*w1; p[k]=t*p1; } else { w[k]=c1*w1; p[k]=c1*p1; } c1=c1-t; t=t*2; k++; } } for(int i=0;i=w[i];j--) { f[j]=max(f[j],f[j-w[i]]+p[i]); } printf("%lldn",f[W]); return 0;}

例题： //HDU 2191 多重背包

#includeint val[110],wei[110],count[110],dp[110];//价格，重量，袋数。动态背包

int max(int a,int b){ return a>b?a:b;}int main(){ int T; scanf("%d",&T); while(T--) { int n,m;// 钱数，种类

scanf("%d%d",&n,&m); for(int i=0;i

for(int i=0;i

for(int k=1;k<=count[i];k++) //⼤⽶ i 放⼊的次数

for(int j=n;j>=val[i];j--) // 动态规划

dp[j]=max(dp[j],dp[j-val[i]]+wei[i]); printf("%dn",dp[n]); //数组dp存的是重量

} return 0;}5 ⼆维费⽤的背包问题5.1 问题⼆维费⽤的背包问题是指：对于每件物品，具有两种不同的空间耗费，选 择这件物品必须同时付出这两种代价。对于每种代价都有⼀个可付出的最⼤值 （背包容量）。问怎样选择物品可以得到最⼤的价值。 设这两种代价分别为代价⼀和代价⼆，第i件物品所需的两种代价分别为Ci和Di。两种代价可付出的最⼤值（两种背包容量）分别为V 和U。物品的 价值为Wi。5.2 算法费⽤加了⼀维，只需状态也加⼀维即可。设F[i,v,u]表⽰前i件物品付出两 种代价分别为v和u时可获得的最⼤价值。状态转移⽅程就是：F[i,v,u] = max{F[i−1,v,u],F[i−1,v−Ci,u−Di] + Wi} 如前述优化空间复杂度的⽅法，可以只使⽤⼆维的数组：当每件物品只可 以取⼀次时变量v和u采⽤逆序的循环，当物品有如完全背包问题时采⽤顺序的 循环，当物品有如多重背包问题时拆分物品。 这⾥就不再给出伪代码了，相信有了前⾯的基础，读者应该能够⾃⼰实现 出这个问题的程序。5.3 物品总个数的限制有时，“⼆维费⽤”的条件是以这样⼀种隐含的⽅式给出的：最多只能 取U件物品。这事实上相当于每件物品多了⼀种“件数”的费⽤，每个物品的 件数费⽤均为1，可以付出的最⼤件数费⽤为U。换句话说，设F[v,u]表⽰付 出费⽤v、最多选u件时可得到的最⼤价值，则根据物品的类型（01、完全、多 重）⽤不同的⽅法循环更新，最后在U]范围内寻找答案。6 分组的背包问题6.1 问题有N件物品和⼀个容量为V 的背包。第i件物品的费⽤是Ci，价值是Wi。这 些物品被划分为K组，每组中的物品互相冲突，最多选⼀件。求解将哪些物品 装⼊背包可使这些物品的费⽤总和不超过背包容量，且价值总和最⼤。6.2 算法这个问题变成了每组物品有若⼲种策略：是选择本组的某⼀件，还是⼀件 都不选。也就是说设F[k,v]表⽰前k组物品花费费⽤v能取得的最⼤权值，则 有： F[k,v] = max{F[k−1,v],F[k−1,v−Ci] + Wi |item i ∈ group k} 使⽤⼀维数组的伪代码如下：

for k = 1 to K

for v = V to 0

for item i in group k

F[v] = max{F[v],F[v−Ci] + Wi}7 有依赖的背包问题7.1 简化的问题这种背包问题的物品间存在某种“依赖”的关系。也就是说，物品i依赖于 物品j，表⽰若选物品i，则必须选物品j。为了简化起见，我们先设没有某个物 品既依赖于别的物品，⼜被别的物品所依赖；另外，没有某件物品同时依赖多 件物品。7.2 算法这个问题由NOIP2006题⽬中⾦明的预算⽅案⼀题扩展⽽来。遵从该题的提 法，将不依赖于别的物品的物品称为“主件”，依赖于某主件的物品称为“附 件”。由这个问题的简化条件可知所有的物品由若⼲主件和依赖于每个主件的 ⼀个附件集合组成。 按照背包问题的⼀般思路，仅考虑⼀个主件和它的附件集合。可是，可⽤ 的策略⾮常多，包括：⼀个也不选，仅选择主件，选择主件后再选择⼀个附 件，选择主件后再选择两个附件……⽆法⽤状态转移⽅程来表⽰如此多的策 略。事实上，设有n个附件，则策略有2n + 1个，为指数级。考虑到所有这些策略都是互斥的（也就是说，你只能选择⼀种策略），所 以⼀个主件和它的附件集合实际上对应于6中的⼀个物品组，每个选择了主件⼜ 选择了若⼲个附件的策略对应于这个物品组中的⼀个物品，其费⽤和价值都是 这个策略中的物品的值的和。但仅仅是这⼀步转化并不能给出⼀个好的算法， 因为物品组中的物品还是像原问题的策略⼀样多。 再考虑对每组内的物品应⽤2.3中的优化。我们可以想到，对于第k个物品组 中的物品，所有费⽤相同的物品只留⼀个价值最⼤的，不影响结果。所以，可 以对主件k的“附件集合”先进⾏⼀次01背包，得到费⽤依次为0...V − Ck所 有这些值时相应的最⼤价值V −Ck]。那么，这个主件及它的附件集合 相当于V −Ck + 1个物品的物品组，其中费⽤为v的物品的价值为Fk[v −Ck] + Wk，v的取值范围是Ck ≤ v ≤ V 。 也就是说，原来指数级的策略中，有很多策略都是冗余的，通过⼀次01背包 后，将主件k及其附件转化为V −Ck + 1个物品的物品组，就可以直接应⽤6的 算法解决问题了。7.3 较⼀般的问题更⼀般的问题是：依赖关系以图论中“森林”1的形式给出。也就是说，主 件的附件仍然可以具有⾃⼰的附件集合。限制只是每个物品最多只依赖于⼀个 物品（只有⼀个主件）且不出现循环依赖。 解决这个问题仍然可以⽤将每个主件及其附件集合转化为物品组的⽅式。 唯⼀不同的是，由于附件可能还有附件，就不能将每个附件都看作⼀个⼀般 的01背包中的物品了。若这个附件也有附件集合，则它必定要被先转化为物品 组，然后⽤分组的背包问题解出主件及其附件集合所对应的附件组中各个费⽤ 的附件所对应的价值。 事实上，这是⼀种树形动态规划，其特点是，在⽤动态规划求每个⽗节点 的属性之前，需要对它的各个⼉⼦的属性进⾏⼀次动态规划式的求值。这已经 触及到了“泛化物品”的思想。看完8后，你会发现这个“依赖关系树”每⼀个 ⼦树都等价于⼀件泛化物品，求某节点为根的⼦树对应的泛化物品相当于求其 所有⼉⼦的对应的泛化物品之和

附加：01背包第k个最优解 思想与01背包相同，不过在动态规划过程中，不可以把前⼀个状态的最优解扔掉，⽽要保存下来。在01背包中，状态数组是 f [ v ] ，表⽰容积为v时的最优决策。⽽现在，我不仅要知道最优决策，我还想知道稍微差⼀点的决策，即第2决策、第3决策....排个名。f [ v ] 我们可以看做是 f [ v ] [ 1 ] 这样的⼆维数组，他的第⼆维只有⼀个元素，也就是最优决策。现在我们增⼤第⼆维，⽐如 f [ v ] [ 3 ] ，意思是，不仅保留了最优解，次解也保留下来了。也可以理解为，第⼆维是⼀个集合，集合⾥就存了所有可能的决策，并按⼤⼩有序，排在第⼀的就是最优解。现在问题是 第k个最优决策是多少。 在01背包⾥，我们只保留了最优解，⽽把不是最优解的解直接舍弃了，即

f[j]=max(f[j],f[j-w[i]]+v[i])这时候，较⼩的那个解直接舍弃了，没保留下来。现在我们要做的就是，借助数组把所有的解都保留下来。核⼼代码： int i,j,t; for(i=0;i=vol[i];j--) //对每个状态进⾏更新

{ for(t=1;t<=k;t++) { //把所有可能的解都存起来 a[t]=f[j][t]; b[t]=f[j-vol[i]][t]+val[i]; } int m,x,y; m=x=y=1; a[k+1]=b[k+1]=-1; //下⾯的循环相当于求a和b并集，也就是所有的可能解

while(m<=k && (a[x]!=-1 || b[y]!=-1)) { if(a[x]>b[y]) f[j][m]=a[x++]; else

f[j][m]=b[y++];

if(f[j][m]!=f[j][m-1]) m++; } }例题：板⼦题）代码：#include

#includeint f[1010][33];//第⼀维和普通01背包⼀样。第⼆维存多个最优解int val[110],vol[110];//价值和体积int a[33],b[33];//⽤于暂时存储多组最优解

int n,v,k;int i,j,t,T;int main(){ scanf("%d",&T); while(T--) { scanf("%d%d%d",&n,&v,&k); for(i=0;i

for(i=0;i=vol[i];j--) //对每个状态进⾏更新

{ for(t=1;t<=k;t++) { //把所有可能的解都存起来 a[t]=f[j][t]; b[t]=f[j-vol[i]][t]+val[i]; } int m,x,y; m=x=y=1; a[k+1]=b[k+1]=-1; //下⾯的循环相当于求a和b并集，也就是所有的可能解

while(m<=k && (a[x]!=-1 || b[y]!=-1)) { if(a[x]>b[y]) f[j][m]=a[x++]; else

f[j][m]=b[y++];

if(f[j][m]!=f[j][m-1]) m++; } } printf("%dn",f[v][k]); } return 0; }