多重背包

多重背包,也就是是01背包的进阶版,但是物品的数目过多,因此把那些数目转化为2的次方数来转存,后续与01背包一致,

下为关键的转化过程

void Slove()
{
int j;
for(int i=1; i<=n; i++)
{
for(j=1; j<=c[i]; j*=2)
{
W[k] = w[i]*j;
P[k] = p[i]*j;
k ++;
c[i] -= j;
}

if(c[i])
{
W[k] = w[i]*c[i];
P[k] = p[i]*c[i];
k ++;
}
}
}

原文地址:https://www.cnblogs.com/zznulw/p/5341921.html