算法设计与分析实验六：使用动态规划算法解决存钱问题（java实现、hdu1114）（csdn）————程序.pdf
版权申诉
193 浏览量
2021-12-05
19:02:53
上传
评论
收藏 91KB PDF 举报
一、实验目的
练习使用动态规划算法解决实际问题（使用 Java 语言实现）
二、实验内容
【问题描述】
给定一个空存钱罐的重量和这个存钱罐最多能装进去的重量，现在需要在不打
破这个存钱罐的情况下猜测里面最少的钱。每种钱的数量不做限制，条件是必
须装满，同时给出每种钱币的价值和重量。
【输入】
输入的第一行数据包含整数 T，表示测试用例的数量。每个测试用例的第一行
都包含两个整数 e 和 f(1<=e<=f<=10000)，分别表示空存钱罐和装满硬币的存
钱罐的重量（以克记）。第二行包含一个整数 n(1<=n<=500),表示硬币的总数
量。接下来的 n 行每行都包含两个整数 p 和 w，分别表示硬币的面值和重量。
【输出】
对每个测试用例，都输出一行，包含”存钱罐内的最小金额是 x“，其中 x 是
存钱罐内的最小金额。若无法确定，则输出”这是不可能的“
样例输入：
3
10 110
2
1 1
30 50
10 110
2
1 1
50 30
1 6
2
10 3
20 4
样例输出
存钱罐内的最小金额是 60
存钱罐内的最小金额是 100
这是不可能
三、程序代码
资源评论
