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

Question

I need some clarification from wikipedia: Knapsack, on the part

This solution will therefore run in O(nW) time and O(nW) space. Additionally, if we use only a 1-dimensional array m[W] to store the current optimal values and pass over this array i+1 times, rewriting from m[W] to m[1] every time, we get the same result for only O(W) space.

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

Please provide some example. Say if I have the set {V,W} --> {(5,4),(6,5),(3,2)} with K = 9.

How would the 1D array look like?

Answer 1

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

Method 1
The straightforward 2D method that uses N rows is:

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][j-w[i]] + v[i]);
        }
    }
    return dp[N][W];
} 

This uses O(NW) space.

Method 2
The second method is also 2D but only uses 2 rows and keep swapping their roles as current & previous row.

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[j-w[i]] + v[i]);
        }
    }
    return dp[N&1][W];
}  

This takes O(2W) = O(W) space. cur is the i-th row and prev is the (i-1)-th row.
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[j-w[i]] + v[i]);
        }
    }
    return dp[W];
}

This also uses O(W) space but just uses a single row. The inner loop has to be reversed because when we use dp[j-w[i]], we need the value from the previous iteration of outer loop. For this the j values have to be processed in a large to small fashion.

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