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

DP,完全背包

1 #include 
     
       2  3 int main() 4 { 5     int t, i, j, n, m, m1, v, w; 6     int dp[10010]; 7     scanf("%d", &t); 8     while(t-- && scanf("%d%d%d", &m1, &m, &n)) 9     {10         m -= m1;11         dp[0] = 0;12         for(i=1; i<=m; i++)13         {14             dp[i] = 12345678;15         }16         for(i=1; i<=n; i++)17         {18             scanf("%d%d", &v, &w);19             for(j=w; j<=m; j++)20             {21                 if(dp[j-w]+v < dp[j])22                 {23                     dp[j] = dp[j-w]+v;24                 }25             }26         }27         if(dp[m] == 12345678)28         {29             printf("This is impossible.\n");30         }31         else32         {33             printf("The minimum amount of money in the piggy-bank is %d.\n", dp[m]);34         }35     }36     return 0;37 }