POJ 1742 coins (二)

using namespace std;

bool F[100001];
int A[101];
int C[101];

int max(int a, int b)
{
return a>b a:b;
}
void ZeroOnePack(int cost, int weight, int V)
{
for (int v=V; v>=cost; --v)
F[v] |= F[v-cost];
}

void CompletePack(int cost, int weight, int V)
{
for (int v=cost; v<=V; ++v)
F[v] |= F[v-cost];
}

void MultiPack(int cost, int weight, int V, int amount)
{
if (cost*amount>=V) {
CompletePack(cost, weight, V);
return;
}
int k = 1;
while (k ZeroOnePack(cost*k, weight*k, V);
amount -= k;
k *= 2;
}
ZeroOnePack(cost*amount, weight*amount, V);
}

int main(int argc, char **argv)
{
int n, m;
while ((cin>>n>>m) && (m+n)) {
for (int i=1; i<=n; ++i)
cin>>A[i];
for (int i=1; i<=n; ++i)
cin>>C[i];

F[0] = 1;
for (int i=1; i<=m; ++i)
F[i] = 0;
for (int i=1; i<=n; ++i)
MultiPack(A[i], A[i], m, C[i]);

int ans=0;
for(int i=1;i<=m;++i)
ans+=F[i];
cout< }
system("pause");
return 0;
}
2329MS险过~