欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

背包dp再学习

程序员文章站 2022-07-12 09:15:06
...

完全背包

题意:

有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(k
weight,kvalue);
number = number-k;
k = 2
k;//这里采用二进制思想
}
ZeroOnePack(numberweight,numbervalue);
}
}

相关标签: 笔记

上一篇: 查找

下一篇: spring 再学习 1