Why do naive solutions of dynamic programming problems take exponential time?

3
votes

I am working on understanding this problem:

You are given a rectangular piece of cloth with dimensions X by Y, where X and Y are positive integers, and a list of n products that can be made using the cloth. For each product i in [1,n] you know that a rectangle of cloth of dimensions ai by bi is needed and that the final selling price of the product is ci. Assume that ai, bi, and ci are all positive integers. You have a machine that can cut any rectangular piece of cloth into two pieces either horizontally or vertically. Design an algorithm that finds the best strategy for cutting an X by Y piece of cloth so that the products made from the resulting pieces give the maximum sum of selling prices. You are free to make as many copies of a given product as you wish, or none if desired.

Although I've actually already properly implemented the dynamic programming solution, I am having a hard time understanding / proving why a naive solution to the problem runs in exponential time. I think this indicates some lack of understanding of exponential algorithms in the first place but I'm mostly concerned with it in the case above for now.

I understand that the dynamic programming solution allows me to save work by memoizing the work that I've already done. The runtime with dynamic programming is supposed to be O((W*H)(n+w+h)) or O(n^3)/polynomial. This is because I am trying each possible width and height of cloth piece. And for each possible width and height of cloth piece I try each possible vertical, horizontal, and piece sized cut. (I'm also a bit confused why n is necessary in the time complexity though because if you try every possible horizontal and vertical cut that should also try every possible piece).

If I turned memoization off, that should give me the brute force method and that involves solving the entire tree. This is supposed to be polynomial or O(2^n). Why? Isn't an algorithm with O(2^n) time complexity supposed to be representable by a binary tree? It seems like a naive solution to this problem wouldn't be binary.

3
algorithmtime-complexitydynamic-programming
You don't want to try every possible cut, because X and Y are independent of n, and could in fact be exponentially larger than n. You limit yourself to the cuts that actually produce a piece of cloth necessary for one of the n products. - chepner
Also, polynomial time is definitely not the same thing as O(2^n). - phs

3 Answers

1
votes

Linear Optimization

  • Solving a problem over 1 variable can be done with Linear Programming\Optimization with,

  • Time: O(n)

  • Space: O(1)

Dynamic Programming

  • Solving a problem over k variables can be done by Dynamic Programming\Optimization with,

  • Time: O(Π{ Si } * T(Δ Ij) * c) for i: 1..k, where Si is the ith variable domain size, and Ij is jth input size, c is "constant" for number of calculations in the model

  • Space: O(Π{ Si }) basically required storage is |S| dimension matrix

Discussion:

~ Basically what you mentioned is the case of 2-variables, an optimal version of a simple Dynamic Programming solving a problem in 2 variables will have a computational time complexity of O((W*H)(n+w+h)) or generally O(3^n) "input size generalized to n"

~ I once wrote a linguistics similarity library using Viterbi Dynamic Programming algorithm using Probabilistic N-gram max-min function over a Hidden Markov Model (stored as a 3D matrix)

~ If you are interested, it's written in Java: download

Sources:

0
votes

This problem sounds like a derivative of the Knapsack problem (ie, get as much worth as possible out of a given amount of space). With that in mind, take a look here. There is a section which explains the naive solution (and represents it with a binary tree), and shows the overlapping sub problems.

If you do not understand how your question is the same as the Knapsack problem, you should start there.

0
votes

to help see why it's 2^n (binary tree), think of the possible cuts as yes/no decisions: do I cut here? or here? or here? Each yes/no binary decision results in a subtree of possibilities that must be examined.

The reason that this problem is not expressed as a binary tree is because we are only interested in the leaves. Specifically, in the optimal leaf. The path from the root to that leaf is the solution of optimal cuts. The tree itself is the possible solution space.