某企业在未来的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)达到同一目标的次佳方法或算法是什么?
理论研究 试验阶段 政府批准 销售
慢 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)达到同一目标的次佳方法或算法是什么?
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 Test {
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);
System.out.println(methods.get(0).getPath()+"-->"+methods.get(0).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+=Test.getValue(paths[i]);
months+=Test.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;
}
}
}
输出结果:
2/10-3/6-2/3-5/8-->27