Given a 2 dimensional array A[n][n] with positive integers. How can I find a path from (1, 1) to (n, n) such that the sum of entries above the path and below the path has the smallest difference (taking absolute value)? The path can only go from (1, 1) to (n, n) moving to right or bottom (but not top or left). Here, (1, 1) denotes the top-left corner and (n, n) denotes the bottom right corner. I’d want to see if a polynomial time solution exists, if not, can we do better than the brute force algorithm using O(2^(2n)*n) time?
I have tried some dp idea like dp[i][j] stores the optimal solution for A[1..i][1..j] but it is not the case that dp[i+1][j] has to use the same path for dp[i][j]. I think I need to do some case handling but I’m not sure how.
>Solution :
This is at least as hard as knapsack problem.
Consider the following variation of the knapsack problem: given weights W1, W2, …, Wn, divide them between two persons, so that the difference in total weights is as small as possible. Here, one person corresponds to taking an item into knapsack, and the other person to leaving it out, and the goal is to get knapsack weight closest to sumW / 2.
Now, in this problem, put the weights W1, W2, …, Wn on the main diagonal of our n-times-n matrix, and make all other elements zeroes. When we draw a path, we can decide for each element independently whether it will be above or below the line we draw. So, if we solve our matrix problem, that will give a solution to the knapsack problem as well.