POJ1384Piggy-Bank（DP）

POJ1384http://poj.org/problem?id=1384

最简单的完全背包问题，注意下初始化为INF就可以。

 #include <map>

 #include <set>

 #include <stack>

 #include <queue>

 #include <cmath>

 #include <ctime>

 #include <vector>

 #include <cstdio>

 #include <cctype>

 #include <cstring>

 #include <cstdlib>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 #define INF 0x3f3f3f3f

 #define MAX(a,b) (a > b ? a : b)

 #define MIN(a,b) (a < b ? a : b)

 #define mem0(a) memset(a,0,sizeof(a))

 typedef long long LL;

 const double eps = 1e-;

 const int MAXN = ;

 const int MAXM = ;

 int T, N, E, F;

 int DP[], P[], W[];

 int main()

 {

     scanf("%d", &T);

     while(T--)

     {

         scanf("%d %d", &E, &F);

         F -= E;

         for(int i=;i<=F;i++) DP[i] = INF;

         scanf("%d", &N);

         for(int i=;i<N;i++) scanf("%d %d", &P[i], &W[i]);

         DP[] = ;

         for(int i=;i<N;i++)

         {

             for(int j=W[i];j<=F;j++)

             {

                 if(DP[j] > DP[j-W[i]] + P[i])

                 {

                     DP[j] = DP[j-W[i]] + P[i];

                 }

             }

         }

         if(DP[F] == INF) printf("This is impossible.\n");

         else printf("The minimum amount of money in the piggy-bank is %d.\n", DP[F]);

     }

     return ;

 }