算法设计与分析实验六：使用动态规划算法解决存钱问题（java实现、hdu1114）

一、实验目的

练习使用动态规划算法解决实际问题（使用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
这是不可能

三、程序代码

package PIGGYBANK;

import java.util.Scanner;

public class PiggyBank {
    private int[] values =new int[501];//硬币面值数组
    private int[] weights=new int[501];//硬币重量数组
    private int[] dp=new int[10001];//dp数组
    private int volume;//存钱罐的容量
    private int n;//硬币种类数量
    Scanner sc=new Scanner(System.in);
    public void total_function(){//整体处理函数
        int T=sc.nextInt();
        while (T!=0){
            T--;
            input();
            dpInit();
            dpSolve();
            output();
        }
    }
    private void input(){//输入函数
        int empty=sc.nextInt();//输入空钱罐的重量
        int full=sc.nextInt();//输入装满硬币的重量
        volume=full-empty;//计算钱罐的容量
        n=sc.nextInt();//输入硬币的种类
        for(int i=0;i 
四、程序运行结果