DPM*_*DPM 6 language-agnostic algorithm dynamic-programming
我最近完成了以下面试练习:
'机器人可以编程为运行"a","b","c"......"n"公里,它分别需要t a,t b,t c ... t n min.一旦运行到程序设计的公里数,它必须关闭"m"分钟.
在"m"分钟之后,它可以再次被编程为运行另一个"a","b","c"......"n"公里.
你会如何编程这个机器人在最短的时间内达到精确的公里数？
我认为这是无界背包问题的一种变体,其中尺寸将是公里数和值,即完成每次拉伸所需的时间.主要区别在于我们需要最小化而不是最大化价值.所以我使用了以下解决方案:http://en.wikipedia.org/wiki/Knapsack_problem#Unbounded_knapsack_problem ,其中我选择了最小值.
最后,因为我们需要一个精确的解决方案(如果有的话),在算法为所有不同距离构建的地图上,我遍历每个机器人的编程距离并找到其中的精确距离和最短时间.
我认为机器人在两次运行之间的暂停是一个红色的鲱鱼,你只需要将它包含在你的计算中,但它不会影响所采用的方法.
我可能错了,因为我没有通过测试.我对预期的解决方案没有任何其他反馈.
编辑:也许我毕竟没错,因为不同的原因我失败了.我只想验证我对这个问题的处理方法.
import static com.google.common.collect.Sets.*;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;
import org.apache.log4j.Logger;
import com.google.common.base.Objects;
import com.google.common.base.Preconditions;
import com.google.common.collect.Lists;
import com.google.common.collect.Maps;
public final class Robot {
static final Logger logger = Logger.getLogger (Robot.class);
private Set<ProgrammedRun> programmedRuns;
private int pause;
private int totalDistance;
private Robot () {
//don't expose default constructor & prevent subclassing
}
private Robot (int[] programmedDistances, int[] timesPerDistance, int pause, int totalDistance) {
this.programmedRuns = newHashSet ();
for (int i = 0; i < programmedDistances.length; i++) {
this.programmedRuns.add (new ProgrammedRun (programmedDistances [i], timesPerDistance [i] ) );
}
this.pause = pause;
this.totalDistance = totalDistance;
}
public static Robot create (int[] programmedDistances, int[] timesPerDistance, int pause, int totalDistance) {
Preconditions.checkArgument (programmedDistances.length == timesPerDistance.length);
Preconditions.checkArgument (pause >= 0);
Preconditions.checkArgument (totalDistance >= 0);
return new Robot (programmedDistances, timesPerDistance, pause, totalDistance);
}
/**
* @returns null if no strategy was found. An empty map if distance is zero. A
* map with the programmed runs as keys and number of time they need to be run
* as value.
*
*/
Map<ProgrammedRun, Integer> calculateOptimalStrategy () {
//for efficiency, consider this case first
if (this.totalDistance == 0) {
return Maps.newHashMap ();
}
//list of solutions for different distances. Element "i" of the list is the best set of runs that cover at least "i" kilometers
List <Map<ProgrammedRun, Integer>> runsForDistances = Lists.newArrayList();
//special case i = 0 -> empty map (no runs needed)
runsForDistances.add (new HashMap<ProgrammedRun, Integer> () );
for (int i = 1; i <= totalDistance; i++) {
Map<ProgrammedRun, Integer> map = new HashMap<ProgrammedRun, Integer> ();
int minimumTime = -1;
for (ProgrammedRun pr : programmedRuns) {
int distance = Math.max (0, i - pr.getDistance ());
int time = getTotalTime (runsForDistances.get (distance) ) + pause + pr.getTime();
if (minimumTime < 0 || time < minimumTime) {
minimumTime = time;
//new minimum found
map = new HashMap<ProgrammedRun, Integer> ();
map.putAll(runsForDistances.get (distance) );
//increase count
Integer num = map.get (pr);
if (num == null) num = Integer.valueOf (1);
else num++;
//update map
map.put (pr, num);
}
}
runsForDistances.add (map );
}
//last step: calculate the combination with exact distance
int minimumTime2 = -1;
int bestIndex = -1;
for (int i = 0; i <= totalDistance; i++) {
if (getTotalDistance (runsForDistances.get (i) ) == this.totalDistance ) {
int time = getTotalTime (runsForDistances.get (i) );
if (time > 0) time -= pause;
if (minimumTime2 < 0 || time < minimumTime2 ) {
minimumTime2 = time;
bestIndex = i;
}
}
}
//if solution found
if (bestIndex != -1) {
return runsForDistances.get (bestIndex);
}
//try all combinations, since none of the existing maps run for the exact distance
List <Map<ProgrammedRun, Integer>> exactRuns = Lists.newArrayList();
for (int i = 0; i <= totalDistance; i++) {
int distance = getTotalDistance (runsForDistances.get (i) );
for (ProgrammedRun pr : programmedRuns) {
//solution found
if (distance + pr.getDistance() == this.totalDistance ) {
Map<ProgrammedRun, Integer> map = new HashMap<ProgrammedRun, Integer> ();
map.putAll (runsForDistances.get (i));
//increase count
Integer num = map.get (pr);
if (num == null) num = Integer.valueOf (1);
else num++;
//update map
map.put (pr, num);
exactRuns.add (map);
}
}
}
if (exactRuns.isEmpty()) return null;
//finally return the map with the best time
minimumTime2 = -1;
Map<ProgrammedRun, Integer> bestMap = null;
for (Map<ProgrammedRun, Integer> m : exactRuns) {
int time = getTotalTime (m);
if (time > 0) time -= pause; //remove last pause
if (minimumTime2 < 0 || time < minimumTime2 ) {
minimumTime2 = time;
bestMap = m;
}
}
return bestMap;
}
private int getTotalTime (Map<ProgrammedRun, Integer> runs) {
int time = 0;
for (Map.Entry<ProgrammedRun, Integer> runEntry : runs.entrySet()) {
time += runEntry.getValue () * runEntry.getKey().getTime ();
//add pauses
time += this.pause * runEntry.getValue ();
}
return time;
}
private int getTotalDistance (Map<ProgrammedRun, Integer> runs) {
int distance = 0;
for (Map.Entry<ProgrammedRun, Integer> runEntry : runs.entrySet()) {
distance += runEntry.getValue() * runEntry.getKey().getDistance ();
}
return distance;
}
class ProgrammedRun {
private int distance;
private int time;
private transient float speed;
ProgrammedRun (int distance, int time) {
this.distance = distance;
this.time = time;
this.speed = (float) distance / time;
}
@Override public String toString () {
return "(distance =" + distance + "; time=" + time + ")";
}
@Override public boolean equals (Object other) {
return other instanceof ProgrammedRun
&& this.distance == ((ProgrammedRun)other).distance
&& this.time == ((ProgrammedRun)other).time;
}
@Override public int hashCode () {
return Objects.hashCode (Integer.valueOf (this.distance), Integer.valueOf (this.time));
}
int getDistance() {
return distance;
}
int getTime() {
return time;
}
float getSpeed() {
return speed;
}
}
}
public class Main {
/* Input variables for the robot */
private static int [] programmedDistances = {1, 2, 3, 5, 10}; //in kilometers
private static int [] timesPerDistance = {10, 5, 3, 2, 1}; //in minutes
private static int pause = 2; //in minutes
private static int totalDistance = 41; //in kilometers
/**
* @param args
*/
public static void main(String[] args) {
Robot r = Robot.create (programmedDistances, timesPerDistance, pause, totalDistance);
Map<ProgrammedRun, Integer> strategy = r.calculateOptimalStrategy ();
if (strategy == null) {
System.out.println ("No strategy that matches the conditions was found");
} else if (strategy.isEmpty ()) {
System.out.println ("No need to run; distance is zero");
} else {
System.out.println ("Strategy found:");
System.out.println (strategy);
}
}
}
稍微简化一下，令 t i为机器人运行距离 d i所需的时间（包括停机时间）。假设 t 1 /d 1 \xe2\x89\xa4 \xe2\x80\xa6 \xe2\x89\xa4 t n /d n。如果 t 1 /d 1明显小于 t 2 /d 2且d 1并且要运行的总距离D很大，则分支定界可能优于动态规划。分支定界求解整数规划公式
\n\n最小化 \xe2\x88\x91 i t i x i
\n服从
\n\xe2\x88\x91 i d i x i = D
\n∀ix i ∈ N
通过使用松弛值（其中 x i可以是任何非负实数）作为指导。通过将x 1设置为D/d 1和∀i \xe2\x89\xa0 1 x i = 0，并且至少 (t 1 /d 1 )D，通过将双程序的唯一变量设置为t 1 /d 1。解决松弛问题是必经步骤；每个整数解都是分数解，因此最佳整数解至少需要时间 (t 1 /d 1 )D 的时间。
\n\n分支步骤采用一个整数程序并将其分成两个，这两个程序的解决方案合在一起覆盖了原始程序的整个解决方案空间。在这种情况下，一个部分可能具有额外约束 x 1 = 0，另一部分可能具有额外约束 x 1 \xe2\x89\xa5 1。看起来这可能会产生带有侧面约束的子问题，但事实上，我们可以删除第一步，或者将 D 减少 d 1并将常数 t 1添加到目标中。分支的另一个选择是添加约束 x i = ⌊D/d i ⌋ 或 x i \xe2\x89\xa4 ⌊D/d i ⌋ - 1，这需要泛化到每个重复次数的上限移动。
\n\n分支定界的主循环选择子问题集合之一，分支，计算两个子问题的边界，并将它们放回集合中。相对于蛮力的效率来自于这样一个事实：当我们有一个具有特定值的解决方案时，每个其松弛值至少为该值的子问题都可以被丢弃。一旦集合以这种方式清空，我们就得到了最优解。
\n\n分支定界和动态编程的混合是可能的，例如，通过 DP 计算小 D 的最佳解决方案，并使用这些值而不是在已解决的子问题上进行分支。
\n