POJ 1742 coins

题意：给出几种面值的钱币和对应的个数，看能否凑出1-m中的各个面值。

分析：显然，多重背包问题。要求全部装满。而且对1-m遍历并计数，毫无压力~

上代码：

[cpp] #include <iostream>
using namespace std;

int MIN_INT = (~(unsigned(-1)>>1));
int 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] = max(F[v], F[v-cost]+weight);
}

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

void MultiPack(int cost, int weight, int V, int amount)
{
    if (cost*amount>=V) {
        CompletePack(cost, weight, V);
        return;
    }
    int k = 1;
    while (k<amount) {
        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, count;
    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];
        count = 0;
        for (int V=1; V<=m; ++V) {
            F[0] = 0;
            for (int i=1; i<=m; ++i)
                F[i] = MIN_INT;
            for (int i=1; i<=n; ++i)
                MultiPack(A[i], A[i], V, C[i]);

            if (F[V]==V)
                ++count;
        }
        cout<<count<<endl;
    }
    system("pause");
    return 0;
}

#include <iostream>
using namespace std;

int MIN_INT = (~(unsigned(-1)>>1));
int 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] = max(F[v], F[v-cost]+weight);
}

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

void MultiPack(int cost, int weight, int V, int amount)
{
if (cost*amount>=V) {
  CompletePack(cost, weight, V);
  return;
}
int k = 1;
while (k<amount) {
  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, count;
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];
  count = 0;
  for (int V=1; V<=m; ++V) {
   F[0] = 0;
   for (int i=1; i<=m; ++i)
    F[i] = MIN_INT;
   for (int i=1; i<=n; ++i)
    MultiPack(A[i], A[i], V, C[i]);

   if (F[V]==V)
    ++count;
  }
  cout<<count<<endl;
}
system("pause");
return 0;
}

好吧~POJ的系统说TLE了~悲剧的一米啊~看了discuss说，这题没那么简单O(V*Σlog n[i])是过不了的~好吧，优化优化~

再分析：

其实上面的程序求出了F[V]的值，这个理论上是不需要的，我们关心F[V]是否等于V而已。这里我们进行优化：

将int F[100001]修改为bool F[100001]，存储F[V]是否等于V

ZeroOnePack和CompletePack可以修改为

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

}

F[v] |= F[v-cost] 直接或运算用0,1表示此价格是否出现过最后上代码：

#include <iostream>[cpp] 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<amount) {
        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;

补充：软件开发 , C++ ,