piggycase_java状态机设计

全栈程序员-站长 • 2022年11月3日下午3:16 • 未分类 • 阅读 0

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全家桶1年46，售后保障稳定

一、实验目的

练习使用动态规划算法解决实际问题（使用Java语言实现）

二、实验内容

【问题描述】

给定一个空存钱罐的重量和这个存钱罐最多能装进去的重量，现在需要在不打破这个存钱罐的情况下猜测里面最少的钱。每种钱的数量不做限制，条件是必须装满，同时给出每种钱币的价值和重量。

【输入】

输入的第一行数据包含整数T，表示测试用例的数量。每个测试用例的第一行都包含两个整数e和f(1<=e<=f<=10000)，分别表示空存钱罐和装满硬币的存钱罐的重量（以克记）。第二行包含一个整数n(1<=n<=500),表示硬币的总数量。接下来的n行每行都包含两个整数p和w，分别表示硬币的面值和重量。

【输出】

对每个测试用例，都输出一行，包含”存钱罐内的最小金额是 x“，其中x是存钱罐内的最小金额。若无法确定，则输出”这是不可能的“

【分析与思考】
由题可知，这是一个完全背包问题。
F-E可以看做背包的重量，硬币可以看做物品。
如果用一维数组求解，则根据完全背包的讲解，在两层for循环中（硬币总重量的for循环 i 以及从前 j 种硬币选择的for循环 j ）需要全部正序遍历。
注意：dp[0]需要初始化为0，因为可能存在这样的情况：硬币总重量为1，有一种重量为1，面值为2的硬币。
那么，此时dp[j]=Math.min(dp[j],dp[j-coins[i].weight]+coins[i].value);求解出来为2。

三、程序代码

package PiggyBank;

import java.util.Scanner;

public class Piggybank { 
   

    private int n;//测试的次数
    private int m;//硬币的种类
    private int e;//存钱罐自身重量
    private int f;//存钱罐装满最大的重量
    private int v;//存钱罐的容量
    private int[] dp=new int[10001];//dp数组
    private int y=0;//标记
    private int[] result;//存贮结果
    Coin[] coins;//硬币的面值和重量数组

    public void inputData() { 
   
        Scanner scanner = new Scanner(System.in);
        System.out.println("请输入测试的次数:");
        n = scanner.nextInt();
        result =new int[n];
        coins =new Coin[1000];
        for(int x =0;x<n;x++){ 
   
            System.out.println("请输入存钱罐自身重量和装满最大的重量:");
            e = scanner.nextInt();
            f = scanner.nextInt();
            v= f-e;
            System.out.println("请输入硬币的种类:");
            m = scanner.nextInt();
            System.out.println("请输入每种硬币的面值和重量:");
            for (int i = 0; i <m; i++) { 
   
                coins[i] =new Coin();
                coins[i].value = scanner.nextInt();
                coins[i].weight = scanner.nextInt();
            }
            load();
        }
        display();
    }

    public void load(){ 
   
        dp[0]=0;
        for(int i=1;i<=v;i++){ 
   
            dp[i]=500000001;
        }
        for(int i=0;i<m;i++){ 
   
            for(int j=coins[i].weight;j<=v;j++){ 
   
                dp[j]=Math.min(dp[j],dp[j-coins[i].weight]+coins[i].value);//状态转移方程
            }
        }
        result[y]=dp[v];
        y++;
    }

    public void display(){ 
   
        System.out.println("结果如下");
        for (int i=0;i<n;i++){ 
   
            if(result[i]!=500000001){ 
   
                System.out.println("存钱罐内的最小金额是"+result[i]);
            }
            else { 
   
                System.out.println("这是不可能的");
            }
        }
    }

    public static void main(String[] args) { 
   
        Piggybank piggybank =new Piggybank();
        piggybank.inputData();
    }

}