piggycase_java状态机设计

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新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();
}
}