1 //Accepted    364 KB    109 ms 2 //多重背包 3 #include <cstdio> 4 #include <cstring> 5 #include <iostream> 6 #include <queue> 7 #include <cmath> 8 #include <algorithm> 9 using namespace std;10 /**11   * This is a documentation comment block12   * 如果有一天你坚持不下去了，就想想你为什么走到这儿！13   * @authr songt14   */15 const int inf = 500000005;16 const int imax_n = 10005;17 int n;18 int weight[505],value[505];19 int dp[imax_n];20 int v;21 int e,f;22 int min(int a,int b)23 {24     return a<b?a:b;25 }26 void Dp()27 {28     for (int i=0;i<=v;i++) dp[i]=inf;29     dp[0]=0;30     for (int i=1;i<=n;i++)31     {32         for (int j=weight[i];j<=v;j++)33         {34             dp[j]=min(dp[j],dp[j-weight[i]]+value[i]);35         }36     }37     if (dp[v]==inf)38     {39         printf("This is impossible.\n");40     }41     else42     {43         printf("The minimum amount of money in the piggy-bank is %d.\n",dp[v]);44     }45 }46 int main()47 {48     int T;49     scanf("%d",&T);50     while (T--)51     {52         scanf("%d%d",&e,&f);53         v=f-e;54         scanf("%d",&n);55         for (int i=1;i<=n;i++)56         scanf("%d%d",&value[i],&weight[i]);57         Dp();58     }59     return 0;60 }