学步园

题目大意：给你一个储蓄罐空的，和满的重量，然后给出各种硬币的价值和对应的重量，要你估计出储蓄罐里面硬币价值和最小为多少，注意要保证重量和恰好为给出满的重量

解题思路：完全背包问题，只是求最小值，注意初始化的处理就可以。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <climits>
#include <algorithm>
using namespace std;

const int maxn = 10100;

int t, empty, full, n, dp[maxn], p[501], w[501];
int main()
{
    
    scanf("%d", &t);
    while(t-- != 0)
    {
        scanf("%d %d", &empty, &full);
        full -= empty;
        scanf("%d", &n);
        for(int i = 0; i < n; i++)
            scanf("%d %d", &p[i], &w[i]);
        for(int i = 1; i <= full; i++)
            dp[i] = INT_MAX ;
        dp[0] = 0;
        for(int i = 0; i < n; i++)
        {
            int tmp = w[i];
            dp[tmp] = p[i];
            while(tmp + w[i] <= full)
            {
                dp[tmp + w[i]] = dp[tmp] + p[i];
                tmp += w[i];
            }
        }
        for(int i = 0; i < n; i++)
        {
            for(int j = w[i]; j <= full; j++)
            {
                if(dp[j - w[i]] != INT_MAX)
                   dp[j] = min(dp[j], dp[j - w[i]] + p[i]);
            }
        }
        if(dp[full] != INT_MAX)
            printf("The minimum amount of money in the piggy-bank is %d.\n", dp[full]);
        else
            printf("This is impossible.\n");
    }
   
    return 0;
}