[Algorithm 101] 0-1 Knapsack Problem

We start this problem with leetcode #494: Target Sum:

You are given a list of non-negative integers, a1, a2, …, an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol.

Find out how many ways to assign symbols to make sum of integers equal to target S.

Assume positive subset P and negative subset N are of one possible way, hence P and N meet the requirement:

sum\left ( P \right ) - sum\left ( N \right ) = S

As the problem implies, the union of subset P and subset N is nums, and the intersection of subset P and subset N is empty(for each element of nums is either positive or negative), so:

sum\left ( P \right ) + sum\left ( N \right ) = sum\left ( nums \right )

So the problem is equivalent to: find subset P from set nums that sum(P) = (S + sum(nums)) / 2, which is a variation of 0-1 knapsack problem.

0-1 Knapsack Problem

Given two integer arrays value[0, …, i – 1] and weight[0, …, i – 1] which represent values and weights associated with i items respectively, and a knapsack of capacity W, find the most valuable subset of the items that fit into the knapsack. We assume here that all the weights and the knapsack’s capacity are positive integers; the items values do not have to be integers.

To design a dynamic programming algorithm, we need to derive a recurrence relation that express a solution to a instance of the knapsack problem in terms of solutions to its smaller subinstances. Let f[i][w] to be the value of an optimal solution to this instance, i.e., the most valuable subset of the first ith items that fit into the knapsack of capacity w.

First, we need to consider some corner cases:

  • f[0][w] = 0(0 <= w <= W ), for i = 0 means when we don’t choose any item, the max value must be 0.
  • f[i][0] = 0(i >= 0), for w = 0 means no capacity is available, the max value must be 0.

For f[i][w](i >= 1), we have two choices:

  • among the subsets that do not include the ith item, the value of an optimal subset is f[i – 1][w];
  • among the subsets that do include the ith item, an optimal subset is made up of this item and an optimal subset of the first i – 1 items that fit into the knapsack of capacity w – weight[i], the value of such an optimal subset is f[i – 1][w – weight[i]] + value[i](w >= weight[i]).

Thus f[i][w] = max{f[i – 1][w] , f[i – 1][w – weight[i]] + value[i] }, the overall formulation is:

f\left [ i \right ]\left [ w \right ] = \left\{\begin{matrix}\\0 & if\ i = 0\ or\ w = 0\\f\left [ i - 1 \right ]\left [ w \right ] & weight\left [ i \right ] > w\\max \left \{ f\left [ i - 1 \right ]\left [ w \right ], f\left [ i - 1 \right ]\left [ w - weight\left [ i \right ] \right ] + value\left [ i \right ] \right \} & weight\left [ i \right ] \leq w\\\end{matrix}\right.

And here is our algorithm:

public class Knapsack {
    static int knapsack(int W, int weight[], int value[]) {
        int f[][] = new int[weight.length + 1][W + 1];

        for (int i = 1; i <= weight.length; i++) {
            for (int w = 1; w <= W; w++) {
                if (weight[i - 1] <= w) {
                    f[i][w] = Math.max(f[i - 1][w], f[i - 1][w - weight[i - 1]] + value[i - 1]);
                } else {
                    f[i][w] = f[i - 1][w];
                }
            }
        }

        return f[weight.length][W];
    }

    public static void main(String[] args) {
        System.out.println(knapsack(5, new int[]{2, 3, 4, 5}, new int[]{3, 4, 5, 6}));
    }
}

Reduce Space Complexity

The method’s space complexity and time complexity are both O(W * weight.length), is there any further optimization?

State f[i][w] is associated with two previous states only: f[i – 1][w] and f[i – 1][w – weight[i]], if f[i – 1][w] and f[i – 1][w – weight[i]] can be kept while calculating f[i][w], space complexity should be reduced to O(W), and this can be achieved by reversing the inner loop:

public class Knapsack {
    static int knapsack(int W, int weight[], int value[]) {
        int f[] = new int[W + 1];

        for (int i = 1; i <= weight.length; i++) {
            for (int w = W; w >= 1; w--) {
                if (weight[i - 1] <= w) {
                    f[w] = Math.max(f[w], f[w - weight[i - 1]] + value[i - 1]);
                }
            }
        }

        return f[W];
    }

    public static void main(String[] args) {
        System.out.println(knapsack(5, new int[]{2, 3, 4, 5}, new int[]{3, 4, 5, 6}));
    }
}

And of course, the if statement can be removed by updating the inner loop condition:

public class Knapsack {
    static int knapsack(int W, int weight[], int value[]) {
        int f[] = new int[W + 1];
        for (int i = 1; i <= weight.length; i++) {
            for (int w = W; w >= weight[i - 1]; w--) {
                f[w] = Math.max(f[w], f[w - weight[i - 1]] + value[i - 1]);
            }
        }
        return f[W];
    }

    public static void main(String[] args) {
        System.out.println(knapsack(5, new int[]{2, 3, 4, 5}, new int[]{3, 4, 5, 6}));
    }
}

A Minor Improvement On Time Complexity

f[W] is what we care, which is affected by state f[W – weight[i – 1]], and f[W – weight[i – 1]] is affected by state f[W – weight[i – 1] – weight[i – 2]], etc. For the kth item, the inner loop end condition can be subjected to max{W – sum{weight[ki]}, weight[i-1]}:

public class Knapsack {
    static int knapsack(int W, int weight[], int value[]) {
        int f[] = new int[W + 1], sum = 0;
        for (int w : weight) sum += w;

        for (int i = 1; i <= weight.length; i++) {
            int bound = Math.max(W - sum, weight[i - 1]);
            for (int w = W; w >= bound; w--) {
                f[w] = Math.max(f[w], f[w - weight[i - 1]] + value[i - 1]);
            }
            sum -= weight[i - 1];
        }

        return f[W];
    }

    public static void main(String[] args) {
        System.out.println(knapsack(5, new int[]{2, 3, 4, 5}, new int[]{3, 4, 5, 6}));
    }
}

Back To Problem Target Sum

Let dp[n] to be count of the possible ways to add up to n, here is the DP solution for the original problem:

public class Solution {
    public int findTargetSumWays(int[] nums, int S) {
        int sum = 0;
        for (int num : nums) sum += num;
        if (sum < S || -sum > S || (sum + S) % 2 == 1) return 0;

        int target = (sum + S) >>> 1, dp[] = new int[target + 1];
        dp[0] = 1;
        for (int num : nums) {
            for (int i = target; i >= num; i--) {
                dp[i] += dp[i - num];
            }
        }
        return dp[target];
    }
}

Leave a Reply

Your email address will not be published. Required fields are marked *

*