Dynamic Programming – How to Apply to Optimization Problems with 2 Constraints

dynamic programming

Suppose you have a collection of blocks, each with a certain height and a certain weight. For example:

Sample input:
(190, 190) (120, 40) (100, 10) (90,130) (70, 40) (60, 70) (30, 30) (10, 90)

Sample output:
4

You want to find the maximum number of blocks you can pile, with 2 constraints: each block must be lighter than the one below it and it must also be shorter than the one below it. How do you solve it?

My approach was to solve it more or less like the knapsack problem. I order the blocks from light to heavier, and I start at the end of the array. Then for each block I am considering, I find the maximum between piling that block and don't piling it, and return it. Here's the C code:

int maxPile(Blocks array[], int block, int maxHeight, int maxWeight){

    /* base case with just 1 block left to consider */
    if (block==0){
        if ((array[0].height < maxHeight) && (array[0].weight < maxWeight))
            return 1;
        else
            return 0;
    }

    /*case where current block can be piled, check the max between piling or not*/
    if ((array[block].height < maxHeight) && (array[block].weight < maxWeight))
        return max(1+maxPile(array,blockk-1,array[block].height,array[block].weight),maxPile(array,block-1,maxHeight,maxWeight));

    /*case where current block can't be piled, so move to next*/
    else
        return maxPile(array,block-1,maxHeight,maxWeight);
}

The algorithm above seems to solve the problem correctly. The problem, as you might have guessed, are the overlapping sub-problems, so the complexity is exponential.

The usual way to solve this is dynamic programming, but I am having a hard time to implement it, specifically because of the 2 constraints.

If there was a single constraint, say weight, I would build a 2-dimensional array where the rows would represent the sub-set of blocks you are working with, and the columns would represent the max weight available.

But with 2 constraints I would need to have a 3-dimensional array to store the solutions of the subproblems, and as soon as the dataset grows a bit this becomes unfeasible.

Another idea I considered was to take the 3 factors (current block, max weight and max height), pass them through a hash function and store the result in a hash table. For some reason this is not working.

Any ideas on how to add dynamic programming to the above solution? (or on how to solve it more efficiently?).

Update: It seems that it's also necessary to sort the array by the second constraint (i.e., height in this case) and run the function again, cause with this order the maximum might be larger.

Best Answer

I fail to see the need for dynamic programming. The following algorithm is O(n^2) in both time and space complexity (could be improved), but gets an exact answer--a significant improvement if you consider that dynamic programming is commonly used to solve problems with exponential complexity.

To start with, place every block on a graph that plots weight vs. height:

points plotted

Next, create a directed graph based on the constraints of the problem (connections go from top-right to bottom left, by necessity):

connected graph

Next, place all nodes with no incoming links into a queue (marked as green--Merry Christmas :) )

queued points

Simple breadth-first search (using your queue as the starting state) should allow you to find the longest path through the graph. The longest path represents the tallest tower possible. No worries about loops, as it is not possible given the constraints of the problem.

We can provide evidence of this algorithm's correctness by proving our initial step:

The base of the optimal tower will be represented by a node with no incoming links. Proof by contradiction: Assume the base node of an optimal tower has an incoming link. The incoming link implies that that node (and by necessity, the entire tower) could be placed on the node that is connected by the incoming node. This tower would be taller than the optimal tower--a contradiction, thus the original assumption must have been wrong.

Let me know if I missed a key point of the problem (or an edge case that is not solved by this method).

Related Topic