各种背包的简要介绍,及模板
- 格式：doc
- 大小：46.00 KB
- 文档页数：3
01背包
什么是01背包？
例子：
有N件物品和一个容量为V的背包。
第i件物品的体积是
c[i]，价值是w[i]。
求解将哪些物品装入背包可使价值总
和最大。
分析：
容量固定，考虑每件物品装与不装，
最优子结构：
若只考虑第i件物品的策略（放或不放），那么就可以转
化为一个只牵扯前i-1件物品的问题
•首先介绍一个状态方程：
f[i][j]=max{f[i-1][j],f[i-1][j-c[i]]+w[i]}
j容量的背包放前i件物品的最大价值。
j（0~v），i（0~n）
如果“不放”第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”，那么价值为f[i-1][v]；
如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”，此时能获得的最大价值就是f[i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。
memset(dp,0,sizeof(dp));
for(i=1;i<=n;i++)
for(j=c[i];j<=V;j++)
dp[i][j]=Max(dp[i-1][j],dp[i-1][j-c[i]]+w[i])；
i表示物品编号，j表示总体积V
c[i]表示物品的体积，w[i]表示物品的价值。
空间优化
memset(dp,0,sizeof(dp));
for(i=1;i<=n;i++)
for(j=V;j>=c[i];j--)
dp[j]=Max(dp[j],dp[j-c[i]]+w[i]);
完全背包
•什么是完全背包？
•例子：
•有N种物品和一个容量为V的背包，每种物品都有无限件可用。
第i种物品的体积是c[i]，价值是w[i]。
求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
•分析：
•这个问题非常类似于01背包问题，所不同的是每种物品有无限件。
也就是从每种物品的角度考虑，与它相关的策略已并非取或不取两种，而是有取0件、取1件、取2件……等很多种
•方程
•f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k*c[i]<=v}
如果理解了01背包，那么完全背包只是它的小小转化，应该不难理解，•这样的算法就达到了O(n*v*k)了，但是还是可以优化成O(n*v),
•伪代码：
•for i=1..N
•for v=0..V
•f[v]=max{f[v],f[v-cost]+weight}
memset(dp,0,sizeof(dp));
for(i=1;i<=n;i++)
for(j=V;j>=c[i];j++)
dp[j]=Max(dp[j],dp[j-c[i]]+w[i]); 01背包
对比
memset(dp,0,sizeof(dp));
for(i=1;i<=n;i++)
for(j=c[i];j<=V;j++)
dp[j]=Max(dp[j],dp[j-c[i]]+w[i]); 完全背包
多重背包
•什么是多重背包？
•例子：
•有N种物品和一个容量为V的背包。
第i种物品最多有n[i]件可用，每件体积是c[i]，价值是w[i]。
求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
•分析：
•完全背包没有个数限制，这个就有个数限制，
•能否用完全背包的思想呢？（是我这句话的意思显然是不能）
•背包九讲里的状态方程：
•f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k<=n[i]}
memset(dp,0,sizeof(dp));
for(i=1;i<=n;i++)
for(k=0;k<=num[i];k++)
for(j=m;j>=c[i]*k;j--)
dp[i][j]=Max(dp[i][j],dp[i-1][j-c[i]*k]+w[i]*k);
复杂度m*num[i]*n
二维费用背包
•二维费用就是取一件物品，要付出两种代价，比如：之前我们有个容量v 可供消耗，那么，再加一种重量u，即一个背包有了两个属性值，v和u，原来它只有一个属性v，物品有了两个属性，那么对应的每种物品的属性也增加了一种即重量，物品就有了三个属性：大小，重量，价值，那么要得到一个物品的价值就要同时花费v和u；这就是所谓的二维费用的概念
•首先：还是来看看我们的01背包代码
for(i=1;i<=n;i++)
for(j=V;j>=w[i];j--)
if(dp[j]<dp[j-w[i]]+v[i])
dp[j]=dp[j-w[i]]+v[i];
其次对比二维费用代码
for(i=1;i<=n;i++)
for(j=V;j>=w[i];j--)//容量的循环
for(k=M;k>=u[i];k--)//多加了一层重量的循环if(dp[j][k]<dp[j-w[i]][k-u[i]]+v[i])
dp[j][k]=dp[j-w[i]][k-u[i]]+v[i];。
