java 算法题，请圣人解决，让大家膜拜一下
java 算法题，请高人解决，让大家膜拜一下
回贴就有分，望大家多多参与。。。。。，最终答案，本人将奉献一百分
题目命名要求：请将编写好的源程序以T+题号的方式命名，例如第1题的源程序保存为“T1.java” ），题目本身有命名要求的除外。
1、 某新建小区要修建多个公共设施，供小区内的居民使用，要求任意2个公共设施之间都要可以互通，可以直接铺一条小路，也可以不直接连通，只要能间接通过小路可达即可。现得到小区物业修路费用统计表，表中列出了任意两公共设施间修建小路的费用，以及该小路是否已经修通的状态。具体要求如下：
a) 公共设施数目N（1< N < 20）；
b) 两个相同公共设施间费用为0；
c) 状态为“已经修通”的公共设施间小路成本为0；
现请设计算法，并编写程序计算出实现目标需要的最低成本，并输出结果。
测试数据文件说明：
测试输入文件命名为“T1_input.in”，每一个测试输入文件包含一个测试用例。每个测试用例的第1行给出公共设施的数目N ( 1< N < 20 )；随后的 N(N-1)/2 行对应公共设施间修建小路的费用及修建状态，每行给4个正整数，数值之间以空格分开，前两个数值代表两个公共设施的编号（从1编号到N），以及修建状态：1表示已建，0表示未建，依次是两公共设施间小路的修建费用。
样例：
输入文件：
3
2 1 0 1
3 1 0 2
3 2 0 4
输出：
最低成本：***
（1）请根据以上要求设计最佳算法，并加以文字说明；
（2）编程实现算法，并以样例文件进行测试，输出结果；
（3）按照下面给定的三个测试数据进行测试，并输出结果。
测试数据一：
4
1 2 0 6
1 3 0 3
1 4 1 8
2 3 0 5
2 4 0 3
3 4 0 4
测试数据二：
5
1 2 0 3
1 3 0 2
1 4 0 4
1 5 1 1
2 3 0 2
2 4 0 3
2 5 0 1
3 4 1 5
3 5 0 4
4 5 0 2
测试数据三：
6
1 2 0 4
1 3 0 2
1 4 0 5
1 5 1 7
1 6 0 3
2 3 0 2
2 4 0 6
2 5 1 2
2 6 0 1
3 4 1 5
3 5 0 4
3 6 0 5
4 5 1 2
4 6 0 3
5 6 0 1
（本题60分，要求1占20分，要求2占10分，要求3占30分）
2、 某军事基地的卫星测控站，需要实时采集卫星的数据并进行测控，测控站要求站内工作人员，每天要24小时不间断测控，由于测控站内需要每天都有部分人员值班，所以每天安排值班人员是一件很重要的事情，不同时间段对值班人员数也有要求，具体要求如下表所示：
每班值班的工作人员分别在6,10,14,18,22,2时开始上班，连续工作8小时。测控站站长需要确定每个班次应派
多少人员值班，才能既满足要求又使每天上班的人数最少。
（1）请根据以上要求设计最佳算法，并加以文字说明；
（2）编程实现算法，并输出每天上班的最少人数；
（3）按照下面给定的新的排班要求运行算法，并输出每天上班的最少人数。
------解决思路----------------------
云青天，我初入江湖，这个真不知道。等云芳来了问他吧。
------解决思路----------------------
有点复杂，看看上班时间有不忙的坛友帮帮你
------解决思路----------------------
不懂 帮你顶！！！
------解决思路----------------------
这种题目是练脑子的
适合没事的时候做。
------解决思路----------------------
算法这种东西。我还是在高中的时候搞过。。后来就没碰过了。。尴尬。
------解决思路----------------------
第二题，我的理解是从任意一个段开始排班！24小时无人结余即最后一个班上完大家都可以下班并且都上满8小时的班！
所以代码如下 ：
就是不知道理解的对不对。
------解决思路----------------------
第一题完全看不懂！！
------解决思路----------------------
最亮的还是你的第一条，JF帮顶走人
------解决思路----------------------
和Java有毛关系，纯算法题目，不会编程语言都可以。
------解决思路----------------------
这东西跟Java没啥关系，就是纯粹数学算法问题；
或者说是运筹学的内容，随便一个往往也是整死个人。
一般来说用穷举方法都能求得最优解，但只怕计算量根本不可实现；
非穷举算法则怕是要：想破脑袋；不过有时候也可以找到相对现成的算法实现。
第一道题属于 图论范畴：最小路径连通图（把所谓修建费换成距离来理解就行了）。
第二道题难度大很多，应该属于规划论范畴：排班算法，往往要用动态规划来解决。
规划论的难度在于：局部最优化解的合集不等于全局最优化解，这个是最TMD让人想死的地方，也就意味着无法简单的进行分而治之、递归啥的就把事情给灭了。无止尽的迭代优化是常用套路，即求得一个解，然后尝试优化它，然后将优化后的作为新解，再尝试优化它；不过很不幸的是，类似于达尔文进化论的缺陷，这种方式仍无法确保得到最优解，因为最优解在其优化过程路径中也许是被淘汰的。
十分有兴趣的同学可以认真学学运筹学，然后再玩玩数学建模竞赛啥的。
------解决思路----------------------
这些题目算法不是关键，而是解题的思路。
可以把费用理解为路径长度。
第一个题目的思路我是这样考虑的：
1、可以证明：最优解肯定是N-1条路径，因为一旦是N条路径，里面肯定有一条路径是多余的。
因此此题可以转化为在N*(N-1)/2条路径中找出(N-1)的最少长度组合，且保证N点全部联通。
2、应该可以证明（但我暂时还没思路证明）：假定一条路径都还未修，那么现在的路径中费用最小的一条肯定在最优解中。
如果以上定律成立，那么算法就很简单了，可以用递归解决：
1、找出最短路径，假定1-2，把1和2看成一个点，因为3无论是和1还是2连都一样。
2、N个点就转化成了N-1个点的问题。递归求解。
------解决思路----------------------
------解决思路----------------------
在学校学《运筹学》的时候做过类似的，但现在忘得差不多了，帮顶
------解决思路----------------------
就是穷举法了 有时间写一下
------解决思路----------------------
楼主，问题一就不要纠结了，我都说了有成熟算法。
你Google下，关键字：“图 最小生成树”
完毕。顺带说下，36的程序我没试过，不过他说的算法是可以的。
大家集中精力玩问题二吧。
另外，穷举的就不那么推荐了，一般情况下的高难度测试数据，用你的PC机是穷举不出来的。
回贴就有分，望大家多多参与。。。。。，最终答案，本人将奉献一百分
题目命名要求：请将编写好的源程序以T+题号的方式命名，例如第1题的源程序保存为“T1.java” ），题目本身有命名要求的除外。
1、 某新建小区要修建多个公共设施，供小区内的居民使用，要求任意2个公共设施之间都要可以互通，可以直接铺一条小路，也可以不直接连通，只要能间接通过小路可达即可。现得到小区物业修路费用统计表，表中列出了任意两公共设施间修建小路的费用，以及该小路是否已经修通的状态。具体要求如下：
a) 公共设施数目N（1< N < 20）；
b) 两个相同公共设施间费用为0；
c) 状态为“已经修通”的公共设施间小路成本为0；
现请设计算法，并编写程序计算出实现目标需要的最低成本，并输出结果。
测试数据文件说明：
测试输入文件命名为“T1_input.in”，每一个测试输入文件包含一个测试用例。每个测试用例的第1行给出公共设施的数目N ( 1< N < 20 )；随后的 N(N-1)/2 行对应公共设施间修建小路的费用及修建状态，每行给4个正整数，数值之间以空格分开，前两个数值代表两个公共设施的编号（从1编号到N），以及修建状态：1表示已建，0表示未建，依次是两公共设施间小路的修建费用。
样例：
输入文件：
3
2 1 0 1
3 1 0 2
3 2 0 4
输出：
最低成本：***
（1）请根据以上要求设计最佳算法，并加以文字说明；
（2）编程实现算法，并以样例文件进行测试，输出结果；
（3）按照下面给定的三个测试数据进行测试，并输出结果。
测试数据一：
4
1 2 0 6
1 3 0 3
1 4 1 8
2 3 0 5
2 4 0 3
3 4 0 4
测试数据二：
5
1 2 0 3
1 3 0 2
1 4 0 4
1 5 1 1
2 3 0 2
2 4 0 3
2 5 0 1
3 4 1 5
3 5 0 4
4 5 0 2
测试数据三：
6
1 2 0 4
1 3 0 2
1 4 0 5
1 5 1 7
1 6 0 3
2 3 0 2
2 4 0 6
2 5 1 2
2 6 0 1
3 4 1 5
3 5 0 4
3 6 0 5
4 5 1 2
4 6 0 3
5 6 0 1
（本题60分，要求1占20分，要求2占10分，要求3占30分）
2、 某军事基地的卫星测控站，需要实时采集卫星的数据并进行测控，测控站要求站内工作人员，每天要24小时不间断测控，由于测控站内需要每天都有部分人员值班，所以每天安排值班人员是一件很重要的事情，不同时间段对值班人员数也有要求，具体要求如下表所示：
每班值班的工作人员分别在6,10,14,18,22,2时开始上班，连续工作8小时。测控站站长需要确定每个班次应派
多少人员值班，才能既满足要求又使每天上班的人数最少。
（1）请根据以上要求设计最佳算法，并加以文字说明；
（2）编程实现算法，并输出每天上班的最少人数；
（3）按照下面给定的新的排班要求运行算法，并输出每天上班的最少人数。
------解决思路----------------------
云青天，我初入江湖，这个真不知道。等云芳来了问他吧。
------解决思路----------------------
有点复杂，看看上班时间有不忙的坛友帮帮你
------解决思路----------------------
不懂 帮你顶！！！
------解决思路----------------------
这种题目是练脑子的
适合没事的时候做。
------解决思路----------------------
算法这种东西。我还是在高中的时候搞过。。后来就没碰过了。。尴尬。
------解决思路----------------------
第二题，我的理解是从任意一个段开始排班！24小时无人结余即最后一个班上完大家都可以下班并且都上满8小时的班！
所以代码如下 ：
public class CSDN2 {
private int num[];
// 当前需要上班的人数
private int need = 0;
// 总共需要的人数
private int total = 0;
//排序次数
private int sort = 0 ;
private boolean go = true ;
public CSDN2() {
num = new int[] { 50, 65, 60, 45, 30, 25 };
}
public static void main(String[] args) {
CSDN2 csdn = new CSDN2();
int min = 1111;
while (csdn.getGo()) {
try {
int num = csdn.digui(csdn.getNum(0), 0);
System.out.println(num);
min = num < min ? num : min;
csdn.sort() ;
} catch (Exception e) {
System.out.println(e.getMessage());
csdn.sort() ;
}
}
System.out.println(min);
}
/**
*
* @param num
* 该班次需要的人数
* @param index
* 第几个班次
* @throws Exception 有结余
*/
public int digui(int num, int index) throws Exception {
need = (num - need ) < 0 ? 0 : (num - need );
System.out.print(need+",");
total = total + need ;
if (index == getLength()-1) {
if(need <= 0 ) {
return 0;
}else {
throw new Exception("无匹配项");
}
}
digui(getNum(index + 1), index + 1);
return total ;
}
public int getLength() {
return num.length;
}
public int getNum(int index) {
return this.num[index];
}
public void sort() {
need = 0 ;
total = 0 ;
++ sort ;
if(sort == getLength()) {
go = false ;
}
int temp = num[0];
for (int i = 1; i < num.length; i++) {
num[i - 1] = num[i];
}
num[num.length - 1] = temp;
}
public boolean getGo() {
return this.go ;
}
}
就是不知道理解的对不对。
------解决思路----------------------
第一题完全看不懂！！
------解决思路----------------------
最亮的还是你的第一条，JF帮顶走人
------解决思路----------------------
和Java有毛关系，纯算法题目，不会编程语言都可以。
------解决思路----------------------
这东西跟Java没啥关系，就是纯粹数学算法问题；
或者说是运筹学的内容，随便一个往往也是整死个人。
一般来说用穷举方法都能求得最优解，但只怕计算量根本不可实现；
非穷举算法则怕是要：想破脑袋；不过有时候也可以找到相对现成的算法实现。
第一道题属于 图论范畴：最小路径连通图（把所谓修建费换成距离来理解就行了）。
第二道题难度大很多，应该属于规划论范畴：排班算法，往往要用动态规划来解决。
规划论的难度在于：局部最优化解的合集不等于全局最优化解，这个是最TMD让人想死的地方，也就意味着无法简单的进行分而治之、递归啥的就把事情给灭了。无止尽的迭代优化是常用套路，即求得一个解，然后尝试优化它，然后将优化后的作为新解，再尝试优化它；不过很不幸的是，类似于达尔文进化论的缺陷，这种方式仍无法确保得到最优解，因为最优解在其优化过程路径中也许是被淘汰的。
十分有兴趣的同学可以认真学学运筹学，然后再玩玩数学建模竞赛啥的。
------解决思路----------------------
这些题目算法不是关键，而是解题的思路。
可以把费用理解为路径长度。
第一个题目的思路我是这样考虑的：
1、可以证明：最优解肯定是N-1条路径，因为一旦是N条路径，里面肯定有一条路径是多余的。
因此此题可以转化为在N*(N-1)/2条路径中找出(N-1)的最少长度组合，且保证N点全部联通。
2、应该可以证明（但我暂时还没思路证明）：假定一条路径都还未修，那么现在的路径中费用最小的一条肯定在最优解中。
如果以上定律成立，那么算法就很简单了，可以用递归解决：
1、找出最短路径，假定1-2，把1和2看成一个点，因为3无论是和1还是2连都一样。
2、N个点就转化成了N-1个点的问题。递归求解。
------解决思路----------------------
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;
public class T1 {
private int pointscount;
private int[][] costs;
private List<int[]> resultlines;
private int maxcost=0;
private List<int[]> groups;
public void addGroup(int p){
groups.add(new int[]{p});
}
public int findPointInGroup(int p){
for (int i=0;i<groups.size();i++){
for (int j=0;j<groups.get(i).length;j++){
if (groups.get(i)[j]==p)
return i;
}
}
return -1;
}
public void inputData(String filename){
BufferedReader br=null;
String str=null;
try {
br = new BufferedReader(new FileReader(filename));
str=br.readLine();
pointscount=Integer.parseInt(str);//读出有多少条点
costs=new int[pointscount+1][pointscount+1];
resultlines=new ArrayList<int[]>();
groups=new ArrayList<int[]>();
for (int i=0;i<pointscount*(pointscount-1)/2;i++){//读每条路径
str=br.readLine();
Scanner scanner=new Scanner(str);
int begin=scanner.nextInt();//起点
int end=scanner.nextInt();//终点
if (begin>end){
int t=begin;
begin=end;
end=t;
}
int done=scanner.nextInt();//已建/未建
int cost=scanner.nextInt();//费用
costs[begin][end]= (done==1?0:cost);//如果已建，可视为费用为0
costs[end][begin]=costs[begin][end];
if (maxcost<costs[begin][end])//记录最大费用
maxcost=costs[begin][end];
if (findPointInGroup(begin)<0){
addGroup(begin);
}
if (findPointInGroup(end)<0){
addGroup(end);
}
}
} catch (FileNotFoundException e) {
e.printStackTrace();
} catch (IOException e) {
e.printStackTrace();
} finally {
try {
br.close();
} catch (IOException e) {
e.printStackTrace();
}
}
}
public int[] minCostInGroup(int b,int e){
int[] line=new int[3];
line[2]=maxcost;
int[] begin=groups.get(b);
int[] end=groups.get(e);
for (int i=0;i<begin.length;i++){
for (int j=0;j<end.length;j++){
if (costs[begin[i]][end[j]]<=line[2]){
line[2]=costs[begin[i]][end[j]];
line[0]=begin[i];
line[1]=end[j];
}
}
}
return line;
}
public void mergeGroup(int[] line){
int bg=findPointInGroup(line[0]);
int eg=findPointInGroup(line[1]);
mergeGroup(bg,eg);
}
/*
public void printGroups(){
System.out.println("-----------------------");
for (int[] p:groups){
for (int x:p){
System.out.print(x+"\t");
}
System.out.println();
}
}*/
public void mergeGroup(int bg,int eg){
int[] bgs=groups.get(bg);
int[] egs=groups.get(eg);
int[] now=new int[bgs.length+egs.length];
System.arraycopy(bgs, 0, now, 0, bgs.length);
System.arraycopy(egs, 0, now, bgs.length, egs.length);
groups.remove(eg);
groups.remove(bg);
groups.add(now);
//printGroups();
}
public void findMinCost(){
List<int[]> lines=new ArrayList<int[]>();
int[] line=null;
for (int i=0;i<groups.size()-1;i++){
for (int j=i+1;j<groups.size();j++){
line=minCostInGroup(i,j);
lines.add(line);
}
}
Collections.sort(lines,new Comparator<int[]>(){
public int compare(int[] o1, int[] o2) {
return o1[2]-o2[2];
}
});
line=lines.get(0);
resultlines.add(line);
mergeGroup(line);
if (groups.size()==1){
int sum=0;
for (int i=0;i<resultlines.size();i++){
sum+=resultlines.get(i)[2];
System.out.println((resultlines.get(i)[0])+"\t"+resultlines.get(i)[1]+"\t"+resultlines.get(i)[2]);
}
System.out.println("最低成本："+sum);
} else {
findMinCost();
}
}
/**
* @param args
*/
public static void main(String[] args) {
T1 t=new T1();
t.inputData("d:\\T1.txt");
t.findMinCost();
}
}
------解决思路----------------------
在学校学《运筹学》的时候做过类似的，但现在忘得差不多了，帮顶
------解决思路----------------------
就是穷举法了 有时间写一下
------解决思路----------------------
楼主，问题一就不要纠结了，我都说了有成熟算法。
你Google下，关键字：“图 最小生成树”
完毕。顺带说下，36的程序我没试过，不过他说的算法是可以的。
大家集中精力玩问题二吧。
另外，穷举的就不那么推荐了，一般情况下的高难度测试数据，用你的PC机是穷举不出来的。