HEU 3014 Piggy-Bank

  

   

    

     

    
    

     

      /***********************************
     
    
   

    

     

    
    

     

      Problem: HEU 3014 Piggy-Bank
     
    
   

    

     

    
    

     

      Time: 0.1010 s
     
    
   

    

     

    
    

     

      Memory: 572 k
     
    
   

    

     

    
    

     

      Accepted Time: 2009-08-06 11:02:19
     
    
   

    

     

    
    

     

      Tip: 完全背包问题
     
    
   

    

     

    
    

     

      dp[i][j]表示前i种硬币重量为j时的价值最小值
     
    
   

    

     

    
    

     

      dp[i][j]=min(dp[i],dp[i][j-w]+p)
     
    
   

    

     

    
    

     

      ************************************/
     
    
   

    

     

    
    

     

      #include <stdio.h>
     
    
   

    

     

    
    

     

      #define MAX 25000000
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	int Case;
     
    
   

    

     

    
    

     
	scanf("%d",&Case);
     
    
   

    

     

    
    

     
	while(Case--)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		int e,f,n,p,w,i,j,dp[10009];
     
    
   

    

     

    
    

     
		scanf("%d%d",&e,&f);
     
    
   

    

     

    
    

     
		int t=f-e;
     
    
   

    

     

    
    

     
		for(i=1;i<=t;i++)dp[i]=MAX;
     
    
   

    

     

    
    

     

      		dp[0]=0;
     
    
   

    

     

    
    

     
		scanf("%d",&n);
     
    
   

    

     

    
    

     
		for(i=1;i<=n;i++)
     
    
   

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     
			scanf("%d%d",&p,&w);
     
    
   

    

     

    
    

     
			for(j=w;j<=t;j++)
     
    
   

    

     

    
    

     
			if(dp[j]>dp[j-w]+p)
     
    
   

    

     

    
    

     

      			dp[j]=dp[j-w]+p;
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
		if(dp[t]<MAX)printf("The minimum amount of money in the piggy-bank is %d./n",dp[t]);
     
    
   

    

     

    
    

     
		else printf("This is impossible./n");
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: blog.csdn.net，作者：万猫学社，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/heihaozi/article/details/4417654