## [Algorithm 101] 0-1 Knapsack Problem

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

You are given a list of non-negative integers, a

_{1}, a_{2}, …, a_{n}, 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:

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:

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 *i*_{th} 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
*i*_{th}item, the value of an optimal subset is f[*i*– 1][*w*]; - among the subsets that do include the
*i*_{th}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:

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 *k*_{th} item, the inner loop end condition can be subjected to max{*W* – sum{weight[*k*…*i*]}, 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]; } }