题目链接：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[][]

相关资源：python入门教程(PDF版)