题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1114

1.问题描述

给出每种硬币的重量与价值，计算储蓄罐中硬币重量为x时，所含硬币的最少总价。每种硬币有无限个。

2.输入

T
E F
N
P1 W1
P2 W2
...
Pn Wn

T：测试用例个数
E:空猪储蓄罐的重量
F:硬币+储蓄罐的重量
N：硬币种类数
Pi ：第i种硬币的价值
Wi：第i种硬币的重量
1 <= E <= F <= 10000

3.输出

输出储蓄罐中硬币的最少价值——“The minimum amount of money in the piggy-bank is XX.”

若无论怎样装硬币都不能让总重恰好为规定的值，则输出“This is impossible.”。

4.示例输入

3
10 110
2
1 1
30 50
10 110
2
1 1
50 30
1 6
2
10 3
20 4

5.示例输出

The minimum amount of money in the piggy-bank is 60.
The minimum amount of money in the piggy-bank is 100.
This is impossible.

6.分析

完全背包。求总重恰好为x时的最少价值。

7.代码

7.1 一维dp[]

7.2二维dp[][]