0/1 Knapsack Dynamic Programming Optimazion, from 2D matrix to 1D matrix

Question

I need to clarify from wikipedia: Knapsack , from the side

This solution will work in O (nW) time and O (nW) space. In addition, if we use only the 1-dimensional array m [W] to store the current optimal values ​​and skip this array i + 1 times, each time rewriting from m [W] to m [1], we get the same result only for spaces O (W).

I'm having trouble understanding how to turn a 2D matrix into a 1D matrix to save space. Also, what does rewriting from m[W] to m[1] every time (or how it works) mean.

Please provide some examples. Say, if I have a set {V, W} → {(5,4), (6,5), (3,2)} with K = 9.

What does a 1D array look like?

Answer 1

In many problems with dynamic programming, you will create a 2D table of rows, where each row depends only on the row that immediately precedes it. In case of a problem with the 0/1 backpack, the repetition (from Wikipedia) is as follows:

m [i, w] = m [i - 1, w] if w _i > w

m [i, w] = max (m [i - 1, w], m [i - 1, w - w _i ] + v _i ) otherwise

Please note that all readings from the table when filling in the row I come only from row i-1; earlier rows in the table are not actually used. Therefore, you can save space in the 2D table by saving only two rows — immediately the previous row and the row you fill. You can optimize this to one row, being a little smarter in the way you populate the entries in the table. This reduces the use of space from rows O (nW) (O (n) and columns O (W)) to O (W) (one or two rows and columns O (W)).

It costs a lot. Many DP algorithms do not explicitly compute the solutions as they become available, but instead populate the table and then perform a second pass through the table at the end to restore the optimal response. If you save only one line, you will get the value of the optimal answer, but you may not know what the optimal answer will be. In this case, you can read the maximum value that you can put in the backpack, but you cannot restore what you have to do to reach this value.

Hope this helps!

Answer 2

I know this is an old question. But I had to spend some time on this, and I'm just documenting the approaches here for any future reference.

Method 1
A direct 2D method that uses N lines:

 int dp[MAXN][MAXW]; int solve() { memset(dp[0], 0, sizeof(dp[0])); for(int i = 1; i <= N; i++) { for(int j = 0; j <= W; j++) { dp[i][j] = (w[i] > j) ? dp[i-1][j] : max(dp[i-1][j], dp[i-1][jw[i]] + v[i]); } } return dp[N][W]; } 

In this case, the space O (NW) is used.

Method 2
The second method is also two-dimensional, but uses only 2 lines and continues to replace its roles with the current and previous.

 int dp[2][MAXW]; int solve() { memset(dp[0], 0, sizeof(dp[0])); for(int i = 1; i <= N; i++) { int *cur = dp[i&1], *prev = dp[!(i&1)]; for(int j = 0; j <= W; j++) { cur[j] = (w[i] > j) ? prev[j] : max(prev[j], prev[jw[i]] + v[i]); } } return dp[N&1][W]; } 

This occupies the space O (2W) = O (W). cur is the i-th line, and prev is the (i-1) -th line.
Method 3
The third method uses a 1D table.

 int dp[MAXW]; int solve() { memset(dp, 0, sizeof(dp)); for(int i =1; i <= N; i++) { for(int j = W; j >= 0; j--) { dp[j] = (w[i] > j) ? dp[j]: max(dp[j], dp[jw[i]] + v[i]); } } return dp[W]; } 

It also uses O (W) space, but just uses one line. The inner loop must be canceled because when we use dp[jw[i]] , we need the value from the previous iteration of the outer loop. For this, the values ​​of j must be processed in a small way.

Test case (from http://www.spoj.com/problems/PARTY/ )

 N = 10, W = 50 w[] = {0, 12, 15, 16, 16, 10, 21, 18, 12, 17, 18} // 1 based indexing v[] = {0, 3, 8, 9, 6, 2, 9, 4, 4, 8, 9} 

answer = 26