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);

}

}