背包dp再学习
完全背包
题意:
有N种物品和一个容量为V的背包,每种物品都有无限件可用。第i种物品的费用是c[i],价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。
分析:
同01背包类似,同样是求背包价值最大的问题,区别在于“每种物品都有无限件可用”。可以转化为01背包:考虑到第i种物品最多选V/c[i]件,于是可以把第i种物品转化为V/c[i]件费用及价值均不变的物品,然后求解这个01背包问题
代码:
for (i=0;i<n;i++)
for (j=w[i];j<=v;j++)
f[j]=max{f[j],f[j-w[i]]+v[i]};
注意:
完全背包与01背包的循环次序相反!!!!
01背包代码:
for (i=0;i<n;i++)
for (j=v;j>=w[i];j++)
f[j]=max{f[j],f[j-w[i]]+v[i]};
多重背包
题意:
有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用,每件费用是c[i],价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大 。
分析:
介于01背包和完全背包之间,重点在于第i种物品最多有n[i]件可用。01背包是每种只有一件,完全背包是每种无限件,而多重背包是每种有限件。
基本算法:
跟完全背包的思路非常类似,需要三个循环,分别是物品种类、背包容量、物品个数;
状态转移方程为:
dp[i][v] = max{dp[i - 1][v - k * c[i]] + w[i] | 0 <=k <= n[i]}
但是因为循环次数过多,当数量特别大的时候会超时,此时就需要转为01背包
转为01背包(用于大数据)
思路:
把第i种物品换成n[i]件01背包中的物品,通过这种方式,将多重背包问题转为物品数为Σn[i]的01背包问题,并利用二进制的思想,来降低复杂度。
以下帮助理解代码:
将第i种物品分成若干件物品,其中每件物品有一个系数,这件物品的费用和价值均是原来的费用和价值乘以这个系数。使这些系数分别为1,2,4,…,2(k-1),n[i]-2k+1,且k是满足n[i]-2^k+1>=0的最大整数。例如,如果n[i]为13,就将这种物品分成系数分别为1,2,4,6的四件物品。分成的这几件物品的系数和为n[i],表明不可能取多于n[i]件的第i种物品。另外这种方法也能保证对于0…n[i]间的每一个整数,均可以用若干个系数的和表示
代码:
void ZeroOnePack(int weight,int value )//01背包
{
int i;
for(i = bag; i>=weight; i–)
{
dp[i] = max(dp[i],dp[i-weight]+value);
}
}
void CompletePack(int weight,int value)//完全背包
{
int i;
for(i = weight; i<=bag; i++)
{
dp[i] = max(dp[i],dp[i-weight]+value);
}
}
void MultiplePack(int weight,int value,int number)//多重背包
{
if(bag<=numberweight)//如果总容量比这个物品的容量要小,那么这个物品可以直到取完,相当于完全背包
{
CompletePack(weight,value);
return ;
}
else//否则就将多重背包转化为01背包
{
int k = 1;
while(k<=number)
{
ZeroOnePack(kweight,kvalue);
number = number-k;
k = 2k;//这里采用二进制思想
}
ZeroOnePack(numberweight,numbervalue);
}
}
上一篇: 查找
下一篇: spring 再学习 1