Dynamic programming: Algorithm to solve the following?

Question

I have recently completed the following interview exercise:

'A robot can be programmed to run "a", "b", "c"... "n" kilometers and it takes t_a, t_b, t_c... t_n minutes, respectively. Once it runs to programmed kilometers, it must be turned off for "m" minutes.

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

How would you program this robot to go an exact number of kilometers in the minimum amount of time?'

I thought it was a variation of the unbounded knapsack problem, in which the size would be the number of kilometers and the value, the time needed to complete each stretch. The main difference is that we need to minimise, rather than maximise, the value. So I used the equivalent of the following solution: http://en.wikipedia.org/wiki/Knapsack_problem#Unbounded_knapsack_problem in which I select the minimum.

Finally, because we need an exact solution (if there is one), over the map constructed by the algorithm for all the different distances, I iterated through each and trough each robot's programmed distance to find the exact distance and minimum time among those.

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

I am probably wrong, because I failed the test. I don't have any other feedback as to the expected solution.

Edit: maybe I wasn't wrong after all and I failed for different reasons. I just wanted to validate 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

Simplifying slightly, let t_i be the time (including downtime) that it takes the robot to run distance d_i. Assume that t₁/d₁ ≤ … ≤ t_n/d_n. If t₁/d₁ is significantly smaller than t₂/d₂ and d₁ and the total distance D to be run are large, then branch and bound likely outperforms dynamic programming. Branch and bound solves the integer programming formulation

minimize ∑_i t_i x_i
subject to
∑_i d_i x_i = D
∀i x_i ∈ N

by using the value of the relaxation where x_i can be any nonnegative real as a guide. The latter is easily verified to be at most (t₁/d₁)D, by setting x₁ to D/d₁ and ∀i ≠ 1 x_i = 0, and at least (t₁/d₁)D, by setting the sole variable of the dual program to t₁/d₁. Solving the relaxation is the bound step; every integer solution is a fractional solution, so the best integer solution requires time at least (t₁/d₁)D.

The branch step takes one integer program and splits it in two whose solutions, taken together, cover the entire solution space of the original. In this case, one piece could have the extra constraint x₁ = 0 and the other could have the extra constraint x₁ ≥ 1. It might look as though this would create subproblems with side constraints, but in fact, we can just delete the first move, or decrease D by d₁ and add the constant t₁ to the objective. Another option for branching is to add either the constraint x_i = ⌊D/d_i⌋ or x_i ≤ ⌊D/d_i⌋ - 1, which requires generalizing to upper bounds on the number of repetitions of each move.

The main loop of branch and bound selects one of a collection of subproblems, branches, computes bounds for the two subproblems, and puts them back into the collection. The efficiency over brute force comes from the fact that, when we have a solution with a particular value, every subproblem whose relaxed value is at least that much can be thrown away. Once the collection is emptied this way, we have the optimal solution.

Hybrids of branch and bound and dynamic programming are possible, for example, computing optimal solutions for small D via DP and using those values instead of branching on subproblems that have been solved.

Answer 2

Create array of size m and for 0 to m( m is your distance) do:

a[i] = infinite;

a[0] = 0;

a[i] = min{min{a[i-j] + t_j + m for all j in possible kilometers of robot. and j≠i} , t_i if i is in possible moves of robot}

a[m] is lowest possible value. Also you can have array like b to save a[i]s selection. Also if a[m] == infinite means it's not possible.

Edit: we can solve it in another way by creating a digraph, again our graph is dependent to m length of path, graph has nodes labeled {0..m}, now start from node 0 connect it to all possible nodes; means if you have a kilometer i you can connect 0 and v_i with weight t_i, except for node 0->x, for all other nodes you should connect node i->j with weight t_j-i + m for j>i and j-i is available in input kilometers. now you should find shortest path from v₀ to v_n. but this algorithm still is O(nm).