动态规划初步之背包问题（参考背包九讲+例题+详细分析+补
充）
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]数组。
0123456789101112 1000888888888 20008810101010181818 30668814141616181824 40669914141717191924 50669914141717192124 626891114161719192124
第⼀⾏和第⼀列为序号，其数值为0)
如m[2][6]，在⾯对第⼆件物品，背包容量为6时我们可以选择不拿，那么获得价值仅为第⼀件物品的价值8，如果拿，就要把第⼀件物品拿出来，放第⼆件物品，价值10，那我们当然是选择拿。m[2][6]=m[1][0]+10=0+10=10；依次类推，得到m[6][12]就是考虑所有物品，背包容量为C时的最⼤价值。
#include <iostream>
#include <cstring>
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<<m[i][j]<<' ';
}
cout<<endl;
}
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<stdio.h>
#include<string.h>
int 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<N;i++)
scanf("%d",v+i);
for(i=0;i<N;i++)
scanf("%d",w+i);
for(i=0;i<N;i++) //第i个物品
for(j=V;j>=w[i];j--){ //j状态的背包（计算重量为j是的最⼤价值）
bag[j]=max(bag[j],bag[j-w[i]]+v[i]);
}
printf("%d\n",bag[V]);
}
return 0;
}
hdu2546
#include<stdio.h>
#include<string.h>
#include<algorithm>
using 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<N;i++)
scanf("%d",v+i);
namespace是干嘛的sort(v,v+N);//通过排序把最贵的菜放到最后⼀个位置
scanf("%d",&m);//把卡余额m看做背包容量
//饭菜的价格即代表他的价值，也代表他的重量
V=m-5;//我们的⽬的是把卡余额尽量刷到5元
if(m<5){
printf("%d\n",m);
continue;
}
for(i=0;i<N-1;i++) //第i个菜
for(j=V;j>=v[i];j--){
bag[j]=max(bag[j],bag[j-v[i]]+v[i]);
}
printf("%d\n",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万元，如何选择项⽬才能使总收益最⼤？
Project Wk Vk A1512 B108 C129 D85结合前⾯两段代码

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。