这道题的题目描述好混乱的说，但是读明白了就能看出来，实际上这道题是一个多重背包，但是，就那么写多重背包必然会超时，所以就有了一个优化，多重背包二进制拆分优化。《背包九讲》中介绍过这种优化，但是昨天看了好久，没明白原理，所以求助+YY，总算是了解了。。所谓二进制拆分优化，就是把n[i]个物品给拆分，每个物品占的空间是c[i]，c[i]*2，c[i]*22，c[i]*23...c[i]*2k-1，c[i]*(n[i]-2k+1)，实际上加和以后还是（c[i]*n[i]），物品的价值也是这么拆分，为什么这么拆分呢？思路来自于二进制数表示法，比如说510=1012，也就是说如果取5件i物品，相当于取第一件和第三件（20+22）所有的数都可以这么表示出来，所以可以说这么拆分了以后和原来是等价的，所以这么拆分当然就是合理的。附AC代码：   view code
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int max(int a, int b)
{
if (a > b) return a;
else return b;
}
int main()
{
int cash, n, cc, c[100000], num[15], t, i, j, tot, dp[100005];
while ((scanf("%d%d", &cash, &n)) != EOF)
{
tot = 0;
memset(c, 0, sizeof(c));
for (i = 1; i <= n; i++)
{
cin >> num[i] >> cc;
if (num[i] != 0)
{
tot++;
c[tot] = cc;
num[i]--;
}
t = 2;
while (num[i] >= t)
{
num[i] -= t;
tot++;
c[tot] = cc * t;
t *= 2;
}
if (num[i] > 0)
{
tot++;
c[tot] = num[i] * cc;
}
}
memset(dp, 0, sizeof(dp));
for (i = 1; i <= tot; i++)
for (j = cash; j >= c[i]; j--)
{
dp[j] = max(dp[j], dp[j - c[i]] + c[i]);
}
cout << dp[cash] << endl;
}
return 0;
}
特别鸣谢：飞哥figo
|