高手来指导一下

Question

那位高手来指导一下，itat的决赛试题怎么备考，给点思路。这主要是考哪方面的内容。
1、 某企业在未来的12个月要研究一种新产品，新产品的研制需要四个阶段，每个阶段都可用慢、正常、快等三种速度进行，时间和成本如下表所列。
理论研究 试验阶段 政府批准 销售
慢 5/5 3/6 6/1 5/8
正常 4/7 2/8 4/1 4/10
快 2/10 1/12 2/3 3/15
说明：单位（月/万元），时间按月，成本按万元为单位。
例如：5/5代表5个月，5万元；4/7代表4个月，7万元。
该企业准备在12个月内花费最少的费用就可以有新产品。
（1）请给出最佳方法或算法。
（2）编程实现最佳算法。
（3）达到同一目标的次佳方法或算法是什么？
-------------------------------------------------------------------
2、 有三个白子和三个黑子如下图布置：
○ ○ ○ ● ● ●
用最少的步数将上图中白子和黑子的位置进行交换：
● ● ● ○ ○ ○
规则是：
（1）一次只能移动一个棋子； 
（2）棋子可以向空格中移动，也可以跳过一个对方的棋子进入空格，但不能向后跳，也不能跳过两个子。
（本题共60分，要求1占30分，要求2占30分）
要求：
（1）分析问题，找出规律，总结出规则和算法，并描述你的算法设计思想。
（2）编程显示每一步交换过程。

Answer 1

第一题代码。封装成一个对象放入集合排序，就可以获得最优解了import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;/*
 * 理论研究 试验阶段 政府批准  销售
 慢 5/5  3/6  6/1  5/8
 正常 4/7  2/8    4/1     4/10
 快 2/10   1/12   2/3     3/15
 */
public class BestMethod {
private static String[] research = new String[] { "5/5", "4/7", "2/10" };
private static String[] test = new String[] { "3/6", "2/8", "1/12" };
private static String[] permit = new String[] { "6/1", "4/1", "2/3" };
private static String[] sale = new String[] { "5/8", "4/10", "3/15" }; public static void main(String[] args) {
HashSet<String> set = new HashSet<String>();
ArrayList<Method> methods = new ArrayList<Method>();
while(set.size()<81){
int i1 = (int) (Math.random()*3);
int i2 = (int) (Math.random()*3);
int i3 = (int) (Math.random()*3);
int i4 = (int) (Math.random()*3);
String path = research[i1]+"-"+test[i2]+"-"+permit[i3]+"-"+sale[i4];
Method method = new Method(path);
if(set.add(path)){
if(method.getMonths()<=12){
methods.add(method);
}
}
}
Collections.sort(methods);
for(int i=0;i<methods.size();i++){
System.out.println(methods.get(i).getPath()+"-->"+methods.get(i).getValue());
}
}

public static Integer getValue(String str) {
String[] strs = str.split("\\/");
return Integer.parseInt(strs[1]);
}
public static Integer getMonth(String str) {
String[] strs = str.split("\\/");
return Integer.parseInt(strs[0]);
}
static class Method implements Comparable<Method>{
private String path;
private Integer months=0;
private Integer value=0; public Method(String path) {
this.path = path;
String[] paths = path.split("-");
for (int i = 0; i < paths.length; i++) {
value+=BestMethod.getValue(paths[i]);
months+=BestMethod.getMonth(paths[i]);
}
} public String getPath() {
return path;
} public void setPath(String path) {
this.path = path;
} public Integer getValue() {
return value;
} public void setValue(Integer value) {
this.value = value;
} @Override
public int compareTo(Method o) {
return this.value.compareTo(o.getValue());
} public Integer getMonths() {
return months;
} public void setMonths(Integer months) {
this.months = months;
}
}
}

Answer 2

第二题,玩过<机械迷城>游戏的人应该有印象

Answer 3

第一题 动态规划加入策略筛选，排除明显非最优子策略以剪枝import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;/* 理论研究 试验阶段 政府批准 销售
 慢 5/5 3/6 6/1 5/8
 正常 4/7 2/8 4/1 4/10
 快 2/10 1/12 2/3 3/15*/
public class Test {
int[][][] data = { { { 5, 5 }, { 4, 7 }, { 2, 10 }, }, 
                   { { 3, 6 }, { 2, 8 }, { 1, 12 }, },
                   { { 6, 1 }, { 4, 1 }, { 2, 3  }, }, 
                   { { 5, 8 }, { 4, 10}, { 3, 15 }, }, };

Map<Integer, Integer> strategyMap0 = new HashMap<Integer, Integer>();
Map<Integer, Integer> strategyMap = new HashMap<Integer, Integer>(); Map<String, String> strategyPathMap = new HashMap<String, String>(); public static void main(String[] args) {
new Test().go();
}

public Map<Integer, Integer> copyMap(Map<Integer, Integer> map2) {
Map<Integer, Integer> map1 = new HashMap<Integer, Integer>();

for(Entry<Integer, Integer> entry : map2.entrySet()) {
map1.put(entry.getKey(), entry.getValue());
}
return map1;
} public void go() {
// initialize the strategymap with the first row
for(int i = 0; i < 3; i++) {
strategyMap.put(data[0][i][0], data[0][i][1]);
strategyPathMap.put(data[0][i][0] + "/" + data[0][i][1], data[0][i][0] + "/" + data[0][i][1]);
}

for(int i = 0; i < 3; i++) {
strategyMap0 = copyMap(strategyMap);
strategyMap.clear();

for(Entry<Integer, Integer> entry : strategyMap0.entrySet()) {
for(int j = 0; j < 3; j++) { int monthsum = entry.getKey() + data[i + 1][j][0];
int moneysum = entry.getValue() + data[i + 1][j][1];

strategyPathMap.put(monthsum + "/" + moneysum, strategyPathMap.get(entry.getKey() + "/" + entry.getValue()) + "-" + (data[i + 1][j][0] + "/" + data[i + 1][j][1]));

// strategy filtering
if(strategyMap.get(monthsum) == null || moneysum < strategyMap.get(monthsum)) {
strategyMap.put(monthsum, moneysum);
}
}
} }

System.out.println(strategyMap.get(12));
System.out.println(strategyPathMap.get(12 + "/" + strategyMap.get(12)));
}}