Dynamic programming: An algorithm for solving the following problems?

Question

I recently completed the following interview:

'The robot can be programmed to start the spaces "a", "b", "c" ... "n" and it takes t _a , t _b , t _c ... t _n minutes, respectively. Once it runs to the programmed kilometers, it should be turned off for minutes "m".

After minutes "m", it can again be programmed to start for additional "a", "b", "c" ... "n" kilometers.

How would you program this robot to the exact number of kilometers in minimal time? ''

I thought this was a variation of the unlimited knapsack problem, in which the size would be the number of kilometers and the value, the time required to complete each section. The main difference is that we need to minimize, not maximize, the value. Therefore, I used the equivalent of the following solution: http://en.wikipedia.org/wiki/Knapsack_problem#Unbounded_knapsack_problem in which I choose the minimum.

Finally, since we need an exact solution (if any), over a map constructed by the algorithm for all different distances, I iterate through each and every programmed distance of the robot to find the exact distance and minimum time between those.

I think that the pause that the robot takes between runs is a small red herring, and you just need to include it in your calculations, but this does not affect the approach taken.

I am probably mistaken because I failed the test. I have no other feedback regarding the expected solution.

Edit: maybe I was not mistaken, and I am not for various reasons. I just wanted to confirm my approach to this 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); } } } 

Answer 1

Simplification of simplification, let t _i be the time (including downtime) that the robot needs to complete the distance d _i . Suppose that t ₁ / d ₁ ≤ ... ≤ t _n / d _n . If t ₁ / d _{1 is} much smaller than t ₂ / d ₂ and d ₁ , and the total distance D that must be started is large, then the branch and snapping are more likely to outperform dynamic programming. Branch and Boundary Decide Integer Programming Formulation

minimize Σ _i t _i x _i
taking into account Σ _i d _i x _i = D
? forall; i x _i & in; <b> N

using the relaxation value, where x _i can be any non-negative real as a guide. The latter is easily verified as a maximum (t ₁ / d ₁ ) D by setting x ₁ to D / d ₁ and & forall; i ≠ 1 x _i = 0 and at least (t ₁ / d ₁ ) D, setting the only variable of the double program to t ₁ / d ₁ . A relaxation decision is a bound step; any integer solution is a fractional solution, therefore, the best integer solution requires a time of at least (t ₁ / d ₁ ) D.

Transition stage takes one whole program and breaks it into two parts, the solutions of which, taken together, cover the entire space of solutions of the original. In this case, one part may have an additional constraint x ₁ = 0, and the other may have an additional constraint x ₁ ≥ 1. It may seem that this will create subqueries with side constraints, but in fact we can simply delete the first move or reduce D by d ₁ and add the constant t ₁ to the target. Another branching option is to add either the constraint x _i = & lfloor; D / d _i & rfloor; or x _i ≤ & lfloor; D / d _i & rfloor; - 1, which requires a generalization to the upper bounds of the number of repetitions of each movement.

The main cycle of branches and borders selects one of a set of subtasks, branches, calculates the boundaries for two subtasks, and puts them back into the collection. Efficiency over brute force comes from the fact that when we have a solution with a certain value, every subtask whose weakened value can at least be thrown out. As soon as the collection is empty this way, we get the optimal solution.

Hybrids of branching and related and dynamic programming are possible, for example, by calculating optimal solutions for small D via DP and using these values ​​instead of branching into subtasks that have been solved.

Answer 2

Create an array of size m and from 0 to m (m is your distance):

a [i] = infinite;

a [0] = 0;

a [i] = min {min {a [ij] + t _j + m for all j in possible kilometers of the robot. and j & ne; i }, t _i if i is in possible movements of the robot}

a [m] is the minimum possible value. You can also have an array of type b to store a[i] . In addition, if [m] == infinite means that this is not possible.

Edit:, we can solve it in another way by creating a digraph, again our graph depends on the path length m , the graph has nodes marked as {0..m}, now starting from node 0 connect it to all possible nodes; means that if you have kilometer i , you can connect 0 and v _i with weight t _i , with the exception of node 0-> x, for all other nodes you must connect node i-> j with weight t _ji + m for j > i and ji are available in input kilometers. you should now find the shortest path from v ₀ to v _n . but this algorithm is still O (nm).

Answer 3

Let G be the desired mileage.

Let n be the longest possible run without a pause.

Let L = G / n (integer arithmetic, the discarded part of the fraction)

Let R = G mod n (i.e., the remainder of the above division)

Make the robot run its longest distance (i.e. n) L times, and then any distance (a, b, c, etc.) is greater than R by the smallest amount (i.e. the smallest available distance equal to or greater than than R)

Either I realized that the problem was wrong, or you all thought about it

Answer 4

I really believe in showing, not telling. Here is a program that can do what you are looking for. Let me know if your question will satisfy your question. Just copy, paste and run the program. You must, of course, test your own data set.

 import java.util.Arrays; public class Speed { /*** * * @param distance * @param sprints ={{A,Ta},{B,Tb},{C,Tc}, ..., {N,Tn}} */ public static int getFastestTime(int distance, int[][] sprints){ long[] minTime = new long[distance+1];//distance from 0 to distance Arrays.fill(minTime,Integer.MAX_VALUE); minTime[0]=0;//key=distance; value=time for(int[] speed: sprints) for(int d=1; d<minTime.length; d++) if(d>=speed[0] && minTime[d] > minTime[d-speed[0]]+speed[1]) minTime[d]=minTime[d-speed[0]]+speed[1]; return (int)minTime[distance]; }// public static void main(String... args){ //sprints ={{A,Ta},{B,Tb},{C,Tc}, ..., {N,Tn}} int[][] sprints={{3,2},{5,3},{7,5}}; int distance = 21; System.out.println(getFastestTime(distance,sprints)); } }