piggycase_java状态机设计

piggycase_java状态机设计一、实验目的练习使用动态规划算法解决实际问题(使用Java语言实现)二、实验内容【问题描述】给定一个空存钱罐的重量和这个存钱罐最多能装进去的重量,现在需要在不打破这个存钱罐的情况下猜测里面最少的钱。每种钱的数量不做限制,条件是必须装满,同时给出每种钱币的价值和重量。【输入】输入的第一行数据包含整数T,表示测试用例的数量。每个测试用例的第一行都包含两个整数e和f(1<=e<=f<=10000),分别表示空存钱罐和装满硬币的存钱罐的重量(以克记)。第二行包含一个整数n(1&

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

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

一、实验目的

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

二、实验内容

  1. 【问题描述】

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

  1. 【输入】

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

  1. 【输出】

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

  1. 【分析与思考】
    由题可知,这是一个完全背包问题。
    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();
}
}

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

四、输出结果

在这里插入图片描述

欢迎前来关注
在这里插入图片描述

在这里插入图片描述

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/234108.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • VBoxManage常用命令「建议收藏」

    VBoxManage常用命令「建议收藏」目录0x01常用命令0x02全部参数0x01常用命令#列出全部虚拟机VBoxManagelistvms#列出全部运行中的虚拟机VBoxManagelistrunningvms#列出虚拟机信息VBoxManageshowvminfouuid|vmname#开启虚拟机VBoxManagestartvmuuid|vmname#…

  • myeclipse添加svn插件「建议收藏」

    myeclipse添加svn插件「建议收藏」转载:http://www.cnblogs.com/xdp-gacl/p/3497016.htmlMyEclipse使用总结——MyEclipse10安装SVN插件一、下载SVN插件subclipse下载地址:http://subclipse.tigris.org/servlets/ProjectDocumentList?folderID=2240在打开的网站中

  • cf名字空格符号复制_字符为空格怎么表示

    cf名字空格符号复制_字符为空格怎么表示CF室内空间的姓名如何打?许多CF游戏玩家在游戏里面常常碰到角色名有空格符的状况,可是在建立CF人物角色的情况下,不管怎样也不可以根据按空白键让自身的姓名有空格符。下边的兔子游戏系列产品详解了怎样在CF游戏角色名字中应用空格符。第一步,保证电脑安裝了智能ABC电脑输入法。如今许多游戏玩家的电脑操作系统全是WIN7,可是WIN7一般沒有安裝智能ABC,因此必须下载一个智能ABC电脑输入法(下…

  • 万字深研:元宇宙应该是生产力工具,而不只是游戏娱乐「建议收藏」

    万字深研:元宇宙应该是生产力工具,而不只是游戏娱乐「建议收藏」元宇宙就是一个筐,大家什么东西都往里面装。出品|Odaily星球日报(ID:o-daily)我是Odaily星球日报的创始人Mandy,Odaily近期与36Kr联合出品…

  • LaTeX 中文段落中显示英文引号的方法

    LaTeX 中文段落中显示英文引号的方法在latex中显示英文引号的方法

  • petalinux-package_centos7安装详细图解

    petalinux-package_centos7安装详细图解PetalLinux是Xilinx公司推出的嵌入式Linux开发工具,专门针对Xilinx公司的FPGASoC芯片和开发板,用户可以在PetaLinux工具的帮助下进行完整的开发流程,包括设计,验证,仿真,下载等。本文将详细介绍PetaLinux的安装流程,虽然实际上基本就是把Xilinx的UG1144翻译一遍。

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号