http://acm.zju.edu.cn/show_problem.php?pid=2014

这些天在做DP专题，所以从HDU转战到ZJU找DP，没想到第一个就A到这道题，感觉有点变态！

这道DP花了我三天时间（资质比较差，没办法），终于搞定了，哈哈！！！

其实前几天我A的几个DP都是一个模板的，核心思想都是一个模板的。而这道题有点区别：

1、题目要求是在存钱罐里存入一定质量的钱，使得最少可以存钱

2、存钱罐必须存满

#include<stdio.h>
#include<string.h>
int p[10001],q[10001];
int price[501],weight[501];
int main()
{
 int i,j,t,w1,w2,w,n;
 scanf("%d",&t);
 while(t--)
 {
  scanf("%d%d",&w1,&w2);
  w=w2-w1;
  memset(p,0,sizeof(p));
  memset(q,0,sizeof(q));
  scanf("%d",&n);
  for(i=0;i<n;i++)
   scanf("%d%d",&price[i],&weight[i]);
  p[0]=1;
  q[0]=0;
  for(i=0;i<n;i++)
  {
   for(j=0;j<=w;j++)
    if(p[j]&&j+weight[i]<=w && (!p[j+weight[i]] || q[j]+price[i] < q[j+weight[i]]))
    {
     q[j+weight[i]]=q[j]+price[i];
     p[j+weight[i]]=1;
    }
  }
  if(p[w]==0)printf("This is impossible.\n");
  else printf("The minimum amount of money in the piggy-bank is %d.\n",q[w]);
 }
 return 0;
}