這道題的題目描述好混亂的說，但是讀明白了就能看出來，實際上這道題是一個多重背包，但是，就那么寫多重背包必然會超時，所以就有了一個優化，多重背包二進制拆分優化。《背包九講》中介紹過這種優化，但是昨天看了好久，沒明白原理，所以求助+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
|