背包问题
动态规划——背包九讲
一、01背包问题
特征：每种物品只有一件
状态方程：f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]} （c[]费用,w[]价值）
解释：f[i][v]表示前i件物品放入容量为v的背包种所能求得的价值最大值
决策为第i件物品放(考虑前i-1件物品放入容量为v-c[i]的背包中)
f[i-1][v]
不放(前i-1件物品放入容量为v的背包中)
f[i-1][v-c[i]]+w[i](第i件物品的价值)
优化：(一维数组)
for(int i=1;i<=n;i++)
for(int j=v;j>=0;j–)
f[j]=max{f[j],f[j-c[i]]+w[i]};//新状态转移方程
细节：是否需要恰好被装满
需要被装满：初始化f[0]=0，f[1…v]=-∞
不需要被装满：初始化f[0…v]=-∞
二、完全背包问题
特征：每种物品有无限件
状态方程：f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k*c[i]<=v}
解释：将完全背包问题转化为01背包问题（拆分物品）
每种物品最多可以放入v/c[i]件，将一种物品拆成v/c[i]件物品，但这样做只是提供了思路，并没有改进时间复杂度
所以将第i件物品拆成2^k件物品保证c[i]*2^k<=v
优化：（一维数组）
for(int i=1;i<=n;i++)
for(int j=0;j<=v;j++)//区别于01背包，这里是因为每种物品有无限件
f[j]=max{f[j],f[v-cost]+weight}
即f[i][v]=max{f[i-1][v],f[i][v-c[i]]+w[i]}.
例题：洛谷p1616疯狂的采药
int main()
{
long i,j,m,n;
long f[1000001],v[1000001],h[1000001];
memset(f,0,sizeof(f));/存放结果的数组置为0
cin>>m>>n;//时间与物品数量
for(i=1;i<=n;i++)
cin>>h[i]>>v[i];//读入重量与价值
for(i=1;i<=n;i++)
for(j=h[i];j<=m;j++)//正序循环
f[j]=max(f[j],f[j-h[i]]+v[i]);//状态转移方程
cout<<f[m];//输出结果
return 0;
}
三、多重背包问题
特征：每种物品有单独的件数
状态方程：f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k<=n[i]}
解释：将完全背包问题转化为01背包问题（拆分物品）
方法是：将第i种物品分成若干件物品，其中每件物品有一个系数，这件物品的费用和价值均是原来的费用和价值乘以这个系数。使这些系数分别为1,2,4,…,2^(k-1),n[i]-2^k+1，且k是满足n[i]-2^k+1>0的最大整数。例如，如果n[i]为13，就将这种物品分成系数分别为1,2,4,6的四件物品。
二进制思想与多重背包问题
问题描述：
假设有1000个苹果，现在要取n个苹果，如何取？正常的做法应该是将苹果一个一个拿出来，直到n个苹果被取出来。
又假设有1000个苹果和10只箱子，如何快速的取出n个苹果呢？可以在每个箱子中放 2^i个苹果，也就是 1、2、4、8、16、32、64、128、256、489（最后的余数），相当于把十进制的数用二进制来表示，取任意n个苹果时，只要推出几只箱子就可以了。
用二进制思想代码（把每n[i] 中的每个物品都当成一个独立的物品，而这 n[i] 个物品能够表示的重量其实用 log n[i]个组合后的物品就能表示。）
int k, t;
k = 1;
t = n[i];
while(t > k)
{
for(j=W; j>=c[i]*k; –j) { f[j] = max(f[j], f[j-c[i] *k] + w[i]*k);
}
t -= k;
k *= 2;
}
for(j=W; j>=c[i]*t; –j) { f[j] = max(f[j], f[j-c[i]*t] + w[i]*t);
}
四、混合三种背包问题
01背包与完全背包的混合
考虑到在P01和P02中给出的伪代码只有一处不同，故如果只有两类物品：一类物品只能取一次，另一类物品可以取无限次，那么只需在对每个物品应用转移方程时，根据物品的类别选用顺序或逆序的循环即可，伪代码如下：
for i=1..N
if 第i件物品是01背包
for v=V..0
f[v]=max{f[v],f[v-c[i]]+w[i]};
else if 第i件物品是完全背包
for v=0..V
f[v]=max{f[v],f[v-c[i]]+w[i]};
再加上多重背包
如果再加上有的物品最多可以取有限次，用P03中将每个这类物品分成O(log n[i])个01背包的物品的方法也已经很优了。
for i=1..N
if 第i件物品是01背包
for v=V..0
f[v]=max{f[v],f[v-c[i]]+w[i]};
else if 第i件物品是完全背包
for v=0..V
f[v]=max{f[v],f[v-c[i]]+w[i]};
else if 第i件物品是多重背包
同上二进制思想与多重背包
五、二维费用的背包问题
特征：每件物品有两种代价
二维费用的背包问题是指：对于每件物品，具有两种不同的费用；选择这件物品必须同时付出这两种代价；对于每种代价都有一个可付出的最大值（背包容量）。问怎样选择物品可以得到最大的价值。设这两种代价分别为代价1和代价2，第i件物品所需的两种代价分别为a[i]和b[i]。两种代价可付出的最大值（两种背包容量）分别为V和U。物品的价值为w[i]。
算法
费用加了一维，只需状态也加一维即可。设f[i][v][u]表示前i件物品付出两种代价分别为v和u时可获得的最大价值。状态转移方程就是：
f[i][v][u]=max{f[i-1][v][u],f[i-1][v-a[i]][u-b[i]]+w[i]}
如前述方法，可以只使用二维的数组：当每件物品只可以取一次时变量v和u采用逆序的循环，当物品有如完全背包问题时采用顺序的循环。当物品有如多重背包问题时拆分物品。
例题：洛谷P1507 NASA的食物计划
int V,W,n,v[530],w[530],k[530],f[530][530];
//V最大体积，W最大质量，n物品个数，vwk每件物品的体积质量卡路里，f状态转移
int main()
{
cin>>V>>W>>n;
for(int i=1;i<=n;i++) cin>>v[i]>>w[i]>>k[i];//输入每件物品的信息
for(int i=1;i<=n;i++) for(int j=V;j>=v[i];j–)
for(int h=W;h>=w[i];h–)
f[j][h]=max(f[j][h],f[j-v[i]][h-w[i]]+k[i]);
cout<<f[V][W];
return 0;
}
六、分组背包问题
特征：每组物品选一件
问题
有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
算法
这个问题变成了每组物品有若干种策略：是选择本组的某一件，还是一件都不选。也就是说设f[k][v]表示前k组物品花费费用v能取得的最大权值，则有：
f[k][v]=max{f[k-1][v],f[k-1][v-c[i]]+w[i]|物品i属于第k组}（还是决策选还是不选）
使用一维数组的伪代码如下：
for 所有的组k
for v=V..0
for 所有的i属于组k
f[v]=max{f[v],f[v-c[i]]+w[i]}
注意：“for v=V..0”这一层循环必须在“for 所有的i属于组k”之外。
Views: 60