问题描述:登山机器人是一个及富挑战性的高技术密集型科学研究项目,它为研究发展多智能体系统和多机器人之间的合作与对抗提供了生动的研究模型。
登山机器人可以携带有限的能量。在登山过程中,登山机器人需要消耗一定能量,连续攀登的路程越长,其攀登的速度就越慢。在对m种不同类型的机器人进行性能测试时,测定出每个机器人连续攀登1,2,…,n米所用的时间。现在要对这m个机器人进行综合性能测试,举行机器人接力连续攀登演习。攀登的总高度为s米。规定每个机器人攀登1次,每次至少攀登1米,最多攀登n米,而且每个机器人攀登的高度必须是整数,即只能在整米处接力。安排每个机器人攀登适当的高度,使完成接力攀登的时间最短。
设计要求:
给定m个登山机器人接力攀登的总高度s,以及每个机器人连续攀登1,2,…,n米所用的时间,计算最优攀登方案。
数据输入:
第1行是正整数m,n和s分别表示机器人的个数、每个机器人最多可以攀登的高度和接力攀登的总高度。接下来的m行中,每行有n个正整数,分别表示机器人连续攀登1,2,…,n米所用的时间。
数据输出:
输出登山机器人接力到达终点的最短攀登时间。
输入样本:(input.txt)
5 10 25
24 49 75 102 130 160 192 230 270 320
23 48 75 103 139 181 224 274 344 415
22 49 80 180 280 380 480 580 680 780
25 51 80 120 170 220 270 320 370 420
23 49 79 118 158 200 250 300 350 400
输出样本:
727
分析:这个问题我们首先想到的是动态规划的策略来解决该问题,然而这里我采用贪吃算法来解决此问题,假设机器人每步走一米,我们进行一米一米的贪吃办法来算出机器人走过的米数,即步数。由于每个机器人都要走,所以我们先让每个机器人走一步,将问题缩小,再在剩下的数据里面选出走下一步用时最少的机器人,让它走一步,进一步缩小问题规模,依次循环直到走完所有的路程,即可求知各个机器人走的步子,即就是走过的路程,对应给出路程的各个机器人的时间叠加起来就得了最短的时间了。
程序黏贴:
package robot;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
public class RobotQuetion {
/**
* @param args
*/
int a[][], times[][];
int n, k, m, time = 0;
public static void main(String[] args) {
RobotQuetion robot = new RobotQuetion();
robot.init();
robot.step1();
robot.stepOthers();
robot.minTime();
robot.saveStep();
System.out.println(robot.getTime());
}
void init() {// 初始化文件数字及存储空间
File file = new File("input.txt");
FileReader rd = null;
try {
rd = new FileReader(file);
} catch (FileNotFoundException e) {
e.printStackTrace();
}
BufferedReader buf = new BufferedReader(rd);
String str = "";
try {
str = buf.readLine();
} catch (IOException e) {
e.printStackTrace();
}
String[] b = str.split(" ");
n = Integer.parseInt(b[0]);
k = Integer.parseInt(b[1]);
m = Integer.parseInt(b[2]);
times = new int[n][];
a = new int[n][];
System.out.println(n + " " + k + " " + m);
for (int i = 0; i < n; i++) {
try {
str = buf.readLine();
} catch (IOException e) {
e.printStackTrace();
}
b = str.split(" ");
times[i] = new int[k + 1];
a = new int[n][2];
for (int j = 1; j <= k; j++) {
times[i][j] = Integer.parseInt(b[j - 1]);
System.out.print(times[i][j] + " ");
}
System.out.println();
}
try {
if (buf.ready())
buf.close();
if (rd.ready())
rd.close();
} catch (IOException e) {
e.printStackTrace();
}
}
void step1() {// 让每个机器人先走一步
for (int i = 0; i < n; i++) {
a[i][0] = times[i][2] - times[i][1];
a[i][1] = 1;
}
}
void stepOthers() {
int flag;
int min;// 最小时间
m -= n;// 已经走了n米
while (m-- > 0) {
min = a[0][0];
flag = 0;
int i;
for (i = 0; i < n; i++)
if (a[i][0] < min && a[i][1] < k) {
min = a[i][0];
flag = i;
}
a[flag][1]++;// 当前机器人向前走一步
if (a[flag][1] < k)
a[flag][0] = times[flag][a[flag][1] + 1]
- times[flag][a[flag][1]];
else
a[flag][0] = 100000000;
}
}
void minTime() {
for (int i = 0; i < n; i++) {
time += times[i][a[i][1]];
System.out.println(a[i][1] + " " + time);
}
}
public int getTime() {
return time;
}
void saveStep() {// 写入到文件
File file = new File("output.txt");
if (!file.exists())
try {
file.createNewFile();
} catch (IOException e1) {
e1.printStackTrace();
}
FileWriter wr = null;
try {
wr = new FileWriter(file);
} catch (IOException e) {
e.printStackTrace();
}
PrintWriter Pw = new PrintWriter(wr, true);
for (int i = 0; i < n; i++) {
Pw.println("第" + (i + 1) + "个机器人走" + a[i][1] + "步 ");
}
Pw.println("总共需要" + getTime() + "单位时间");
}
}
分享到:
相关推荐
人工智能机器人alice的java版源代码Alice人工智能机器人alice的java版源代码Alice
卡雷尔机器人学Java
根据网页版微信协议实现的Java版微信机器人,项目是开源的,自己改了一些东西在里面,
网络机器人java编程指南,网络机器人java编程指南网络机器人java编程指南网络机器人java编程指南网络机器人java编程指南网络机器人java编程指南网络机器人java编程指南
卡雷尔机器人学JAVA(KAREL THE ROBOT LEARNS JAVA) 可复制版
4.参数使用的是JSONObject,防止在用字符串拼接参数时出现各种特殊字符转义问题; 5.发送图片大小不超过2M(企业微信的规定)。 具体使用步骤见博客:...
网络机器人 java编程指南 用java实现网络机器人、自动执行复杂的Web交互
1. 主要包含3个java文件Robot.java, TextMessage.java, Utils.java 2. 网上拷贝可用的代码,只需更改机器人地址即可. 3. 包含httpclient jar包,fastjson jar包等.
根据网上aiml机器人开发的资料,整合的一个问答机器人demo,已解决中文支持问题,基于java开发,并附送2个文档
Java LEGO 机器人 编程教程 英文版 JAVA无线控制机器人
仿京东智能客服的,里面有源码及各种注释,适合小白入手学习
卡雷尔机器人学JAVA(KAREL THE ROBOT LEARNS JAVA)
Java虚拟网络机器人源代码
网络机器人JAVA编程指南
网络机器人Java编程指南,指导你如何用Java进行网络机器人的设计、编写
主要是写百度语音appKey信息, 图灵机器人。 运行 找到 robot-runner/target/robot-runner-jar-with-dependencies.jar 上传到你自己的树莓派上。 将profile.yml复制到树莓派上robot-runner-jar-with-dependencies....
该机器人 基于java编程结合 图灵robot 和百度语音SDK制作,实现智能聊天,用于课程设计,或作业娱乐
网络机器人Java编程指南,详细讲了网络机器人和搜索引擎设计。。
站长机器人2.2版破解版 站长机器人2.2版破解版站长机器人2.2版破解版