hdu 2844 Coins 多重背包优化 很好

/*

下面给出O(log amount)时间处理一件多重背包中物品的过程，其中amount表示物品的数量：

procedure MultiplePack(cost,weight,amount)

if cost*amount>=V

CompletePack(cost,weight)

return

integer k=1

while k<amount

ZeroOnePack(k*cost,k*weight)

amount=amount-k

k=k*2

ZeroOnePack(amount*cost,amount*weight)

*/

#include <iostream>//2585875 2010-07-10 22:43:25 Accepted 2844 234MS 624K 1067 B C++ 悔惜晟

#include <cstdio>

#include <cstring>

using namespace std;

int dp[100005];

int m;

void compelete(int cost, int weight)

{

for(int i = cost; i <= m; i++)

if(dp[i] < dp[i - cost] + weight)

dp[i] = dp[i - cost] + weight;

}

void one_zero(int cost, int weight)

{

for(int i = m; i >= cost; i--)

if(dp[i] < dp[i - cost] + weight)

dp[i] = dp[i - cost] + weight;

}

int main()

{

int a[105];

int c[105];

int n;

while(cin >> n >> m)

{

if(n == 0 && m == 0)

break;

for(int i = 1; i <= n; i++)

cin >> a[i];

for(int j = 1; j <= n; j++)

cin >> c[j];

memset(dp, 0, sizeof(dp));

for(int i = 1; i <= n; i++)

{

int tt = a[i] * c[i];

int t = c[i];

if(tt > m)

compelete(a[i], a[i]);//完全背包

else

{

int k = 1;// 0 - 1 背包

while(k < t)

{

one_zero(k * a[i], k*a[i]);

t -= k;

k *= 2;

}

one_zero(t * a[i], t * a[i]);

}

}

int count = 0;

for(int i = 1; i <= m; i++)

if(dp[i] == i)

count++;

printf("%d/n", count);

}

} /*

又是一道多重背包的变形，一开始转化为0-1背包连sample都没有过了，后来用了母函数，看看复杂程度

超时是难免的，最后还是要用多重背包，但是用了优化

将第i种物品分成若干件物品，其中每件物品有一个系数，

这件物品的费用和价值均是原来的费用和价值乘以这个系数。

使这些系数分别为 1,2,4,...,2^(k-1),n[i]-2^k+1，且k是满足n[i]-2^k+1>0的最大整数

例如，如果n[i]为13，就将这种 物品分成系数分别为1,2,4,6的四件物品。

*/

#include <iostream>//2585494 2010-07-10 20:45:20 Accepted 2844 437MS 276K 1446 B C++ 悔惜晟

#include <cstdio>

#include <algorithm>

using namespace std;

const int N = 105;

int main()

{

int n, m;

int val[N], kind[N];

while(scanf("%d %d", &n, &m) != EOF)

{

if(n == 0 && m == 0)

break;

for(int i = 1; i <= n; i++)

scanf("%d", &val[i]);

//int m1 = 0;

for(int i = 1; i <= n; i++)

{

scanf("%d", &kind[i]);

//m1 += val[i] * kind[i];

}

bool dp[100005];

/* 母函数 TLE

int c1[100005];

int c2[100005];

memset(c1, 0, sizeof(c1));

memset(c2, 0, sizeof(c2));

c1[0] = 1;

for(int i = 1; i <= n; i++)

{

for(int j = 0; j <= kind[i]; j++)

for(int k = 0; k <= m; k++)

if(k + j * val[i] <= m)

c2[k + j * val[i]] += c1[k];

else

break;

for(int j = 0; j <= m; j++)

{

c1[j] = c2[j];

c2[j] = 0;

}

}

int count = 0;

for(int i = 1; i <= m; i++)

if(c1[i] != 0)

count++;

printf("%d/n", count);

*/

memset(dp, false, sizeof(dp));

dp[0] = true;

for(int i = 1; i <= n ; i++)

{

int tt = kind[i];

for(int j = 1; j <= tt; j <<= 1)

{

for(int k = m; k >= j * val[i]; k--)

if(dp[k - j * val[i]])

dp[k] = true;

tt -= j;

}

if(tt != 0)

{

for(int k = m; k >= tt * val[i]; k--)

if(dp[k - tt * val[i]])

dp[k] = true;

}

}

int count1 = 0;

for(int i = 1; i <= m; i++)

if(dp[i])

count1++;

printf("%d/n", count1);

}

}