POJ 1384 PigBank

题意：题目的意思是有一个储蓄罐，里面放了硬币，只知道储蓄罐装了硬币和没装硬币时的重量，并且知道每种面值硬币的重量。现在要求储蓄罐中可能的最小金额。若储蓄罐中硬币的重量和每种面值硬币的重量不能匹配，则输出impossible。

分析：这又是一道典型的完全背包问题，因为我们可以认为储蓄罐中每种面值的钱币是任意多的。这道题只是把求最大值改为了求最小值。并且背包要求完全装满。这个时候要注意初始化的时候不能初始为负无穷而应该是正无穷了。但是我们不能这么定义：

[cpp]
#define MAX_INT 0x7fffffff

#define MAX_INT 0x7fffffff

因为若是这么定义在计算F[v-cost]+weight时F[]会溢出，因为是做加法，这一点应该特别注意。我们应该定义MAX_INT为F[]可能的最大值。F[]的含义是前i件物品恰放入一个容量为v的背包可以获得的最小价值。现在v的最大值是10000，钱币的最轻重量是1，就是说最多可能有10000个钱币，钱币的最大面值是50000，也就是说，F[]的最大值是500000000。所以我们应该

[cpp]
#define MAX_INT 500000000

#define MAX_INT 500000000

见代码：

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

#define MAX_INT 50000000

int F[10001];
int P[501];
int W[501];

int min(int a, int b)
{
    return a<b?a:b;
}

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

int main(int argc, char **argv)
{
    int T, a, b, V, n;
    cin>>T;
    while (T--) {
        cin>>a>>b;
        V = b - a;
        cin>>n;
        F[0] = 0;
        for (int i=1; i<=10000; ++i)
            F[i] = MAX_INT;
        for (int i=1; i<=n; ++i) {
            cin>>P[i]>>W[i];
            CompletePack(W[i], P[i], V);
        }


        if (F[V]==MAX_INT)
            cout<<"This is impossible."<<endl;
        else
            cout<<"The minimum amount of money in the piggy-bank is "<<F[V]<<"."<<endl;

    }
    system("pause");
    return 0;
}

#include <iostream>
using namespace std;

#define MAX_INT 50000000

int F[10001];
int P[501];
int W[501];

int min(int a, int b)
{
return a<b?a:b;
}

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

int main(int argc, char **argv)
{
int T, a, b, V, n;
cin>>T;
while (T--) {
  cin>>a>>b;
  V = b - a;
  cin>>n;
  F[0] = 0;
  for (int i=1; i<=10000; ++i)
   F[i] = MAX_INT;
  for (int i=1; i<=n; ++i) {
   cin>>P[i]>>W[i];
   CompletePack(W[i], P[i], V);
  }

  if (F[V]==MAX_INT)
   cout<<"This is impossible."<<endl;
  else
   cout<<"The minimum amount of money in the piggy-bank is "<<F[V]<<"."<<endl;

}
system("pause");
return 0;
}

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