有N种物品,每种物品的数量为C1,C2......Cn。从中任选若干件放在容量为W的背包里,每种物品的体积为W1,W2......Wn(Wi为整数),与之相对应的价值为P1,P2......Pn(Pi为整数)。求背包能够容纳的最大价值。
我们可以转化成01背包来做,但是这样很慢。
所以我们可以二进制优化。
一个数a,我们可以按照二进制来分解为1 + 2 + 4 + 8 …… +2^n + 剩下的数 = a
剩下的数等于a - (1 + 2 + 4 + 8 …… +2^n )
我们把a拆成这么多项,可以证明,这么多项可以组合出1~a的每一个数
所以我们就可以把数量拆分,分成一些物品。这样会快很多。
#include<cstdio>
#include<algorithm>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;
const int MAXN = 112;
const int MAXM = 51234;
int f[MAXM], v[MAXN * 10], w[MAXN * 10];
int n, m, N;
void add(int ww, int vv, int cc) //拆分
{
int now = 1;
while(1)
{
if(cc <= now)
{
w[N] = ww * cc;
v[N++] = vv * cc;
break;
}
else cc -= now;
w[N] = ww * now;
v[N++] = vv * now;
now <<= 1;
}
}
int main()
{
scanf("%d%d", &n, &m);
REP(i, 0, n)
{
int ww, vv, cc;
scanf("%d%d%d", &ww, &vv, &cc);
add(ww, vv, cc);
}
REP(i, 0, N)
for(int j = m; j >= w[i]; j--)
f[j] = max(f[j], f[j - w[i]] + v[i]);
printf("%d\n", f[m]);
return 0;
}