hdu 1114

地址：http://acm.hdu.edu.cn/showproblem.php?pid=1114

题意：小盆友通过往猪猪存钱罐里放钱的方式攒钱做事。存钱罐除非砸坏，否则无法把钱取出。为了知道是否攒了足够的钱，对存钱罐称重。然后告诉每种钱币的重量和价值，问存钱罐里最少可能有多少钱。

mark：算是一个比较裸的完全背包问题。只不过是选最小。

代码:

 1 # include <stdio.h>
 2 # include <string.h>
 3 
 4 
 5 int n, m, INF = 0x3f3f3f3f ;
 6 int p[510], w[510] ;
 7 int dp[10010] ;
 8 
 9 
10 int min(int a, int b){return a<b?a:b;}
11 
12 
13 void work()
14 {
15     int i, j ;
16     memset (dp, 0x3f, sizeof(dp)) ;
17     dp[0] = 0 ;
18     for (i = 0 ; i < n ; i++)
19         for (j = w[i] ; j <= m ; j++)
20             dp[j] = min(dp[j], dp[j-w[i]]+p[i]) ;
21     if (dp[m] == INF) puts ("This is impossible.") ;
22     else printf ("The minimum amount of money in the piggy-bank is %d.
", dp[m]) ;
23 }
24 
25 
26 int main ()
27 {
28     int T, e, f, i ;
29     scanf ("%d", &T) ;
30     while (T--)
31     {
32         scanf ("%d%d", &e, &f) ;
33         m = f-e ;
34         scanf ("%d", &n) ;
35         for (i = 0 ; i < n ; i++)
36             scanf ("%d%d", &p[i], &w[i]) ;
37         work() ;
38     }
39     return 0 ;
40 }