Assume we have the following problem:
There are m places in a street:
p1,p2,...,pm (each place has a weight)
where we can place k stores:
s1,s2,...,sk (each store has a weight).
Placing a store si on place pj comes with a cost of:
k(si,pj)=si*pj.
How could one design a dynamic programming algorithm in order to solve the problem:
Place all the stores in a way that the total cost SUM(k(si,pj)) is minimal + the stores have to be placed in order, i.e. store s4 on place p2 and s2 on place p5 is not valid!
I was trying to think about a solution with recursion. Because with the recursive solution, it should be 'easy' to transform the algorithm into a dynamic programming algorithm (don't need to explain this). But still I can't even figure it out how to solve this with recursion (e.g. how to split this in subproblems?). Can someone give me a hint?
Yep, this is surely DP. As with all DP problems, figuring out the problem is largely figuring out the OPT matrix. In this case, we have two dimensions: subsegment of the road and number of stores placed.
Consider a solved problem, but you're now given one more store (k+1) to add. You have j options of where that store goes, where j = m - p(sk), p(sk) being the placement of store k.
So, let OPT be a matrix of size (m+1) x (k +1), where OPT[i,j] is the optimal cost of placing j signs using up to i locations. The rows are 0...m, and the columns are 0...k, because the placement of 0 signs is a valid sub problem.
Initialize the trivial subproblems first: OPT[i,0] = 0 for all i, because the cost of placing 0 stores is 0. If you really care about the running speed you could also initialize OPT[i,i] = sum of costs(sj, pj), 0 < j <= i for all i, but this doesn't change the algorithmic complexity so it will be left out.
Then, you can use the recurrence
OPT[i,j] =
if j > i
infty
else
min of k in [0, i) of
OPT[k, (j-1)] + min of z in (k,i] of COST(sj, pz)
Where COST(sj, pz) is the cost of placing store j at place z.
To restate in English: The optimal way to place j stores using the segment [0, i] of the road is equivalent to the best (minimum cost) way to place (j-1) stores in some sub segment of the road [0,k] plus the cost placing the jth store somewhere in the remaining sub segment (k, i]. Optimizing over both of these loops gives the optimal solution for the problem of size i, j.
This respects your invariant because it only places new stores after already placed stores.
When you've filled out OPT, just return OPT[m,k], the optimal cost of placing k signs up to location m.
The algorithm has time complexity O(m^4), because calculating a single element of OPT has a pair of nested for loops, both of which are bounded by m, and OPT is bounded by m^2 non trivial entries. (k is bounded by m because a problem in which k > m is not valid. You can't place 10 stores on 8 spots on a road.) For comparison, the brute force method is m choose k, which is much worse (not polynomial).
Your question doesn't have a language tag, so here's an implementation in java:
class StorePlacer{
/** Solves the Store Placement problem for the given values of m, k, and cost
* @param m - number of places to put a store on the street.
* @param k - number of stores to place
* @param cost - a matrix of placement costs.
* cost[i][j] = the cost of placing store j at location i
* cost.length must equal m,
* cost[i].length must equal k for all i in [0, m-1].
* @return - the optimal (minimum) cost of placing k stores on the road of length m.
*/
public static int solve(int m, int k, int[][] cost){
//Check preconditions.
assert(m == cost.length);
for(int[] i : cost){
assert(k == i.length);
}
int[][] opt; //The optimum matrix. Has size (m+1)x(k+1).
//Col i = segment of road [0, i].
//Row j = placing j stores.
//Initialize opt to correct size, fill with initial values
opt = new int[m+1][k+1];
for(int r = 0; r < opt.length; r++){
for(int c = 0; c < opt[r].length; c++){
if(c == 0)
opt[r][c] = 0; //Trivial Problem - 0 signs, 0 cost
else
opt[r][c] = Integer.MAX_VALUE / 2; //Unsolved problem
}
}
//Iteratively solve by moving left along each row in turn.
//Could be done recursively to achieve the same affect.
//Start at col 1 because col 0 is all trivial problems.
for(int r = 0; r < opt.length; r++){
for(int c = 1; c < opt[r].length; c++){
if(r >= c){
//Best cost encountered for this cell thus far.
// Set to infty / 2 to prevent overflow.
int bestTotalCost = Integer.MAX_VALUE / 2;
//For each subsegment of the road [0 .. x]
for(int x = 0; x < r; x++){
//Find the optimal place to put the new store on the other subsegment
int bestSingleCost = Integer.MAX_VALUE / 2;
//y here is where you are placing the next store.
for(int y = x+1; y <= r; y++){
if(cost[y-1][c-1] < bestSingleCost)
bestSingleCost = cost[y-1][c-1];
}
int totalCost = bestSingleCost + opt[x][c-1];
if(totalCost < bestTotalCost)
bestTotalCost = totalCost;
}
opt[r][c] = bestTotalCost;
}
else{
opt[r][c] = Integer.MAX_VALUE / 2; //Impossible problem - more stores than locations
}
}
}
return opt[m][k];
}