0/1 Knapsack

0/1 Knapsack

Given a backpack with capacity K and a list of n items (each item_i has a size k_i), find a subset of items whose total size equal to K or determine no such subset exists.

Example

I: [2, 3, 5, 7], 11
O: False
I: [2, 3, 5, 7], 10
O: True

Brute Force Approach

We can try all possible subsets, then check their sum. But this will be EXP time. Not desired.

DP Approach

Since the problem is asking for doability (a form of optimization), we can try to do DP on size.

Step 1 Define optimal subproblem
KP(n,k) = can these n items that fit in capacity k

Step 2 Solve by prefix
KP(i,k) = OR(KP(i-1, k), KP(i-1, k - k_i))

Step 3 Base cases
KP(0,0) = T
KP(0,k) = 0 for 1 <= k <= K

Step 4 Topo Order
for i from 1 to n
for k from 0 to K

Step 5 Final answer
KP(n,K)

DP Code

public boolean backpack1(int K, int[] items) {
   // create memo table
   int n = items.length;
   boolean[][] KP = new boolean[n+1][K+1];
   // init base cases
   KP[0][0] = true;
   // optional
   for (int k = 1; k <= K; k++) KP[0][k] = false;
   // topo order
   for (int i = 1; i <= n; i++) {
       for (int k = 0; k <= K; k++) {
           int ri = i - 1;
           KP[i][k] = KP[i-1][k];
           if (k - items[ri] >= 0)
                KP[i][k] = KP[i][k] || KP[i-1][k-items[ri]];
       }
   }
   // final answer
   return KP[n][K]; 
}

Variant I (LI.92)

The new objective is to pack the bag as full as possible. Just scan the last row in the memo table.

for (int k = K; k > 0; k--) {
    if (KP[n][k]) return k;
}

Space Optimization

Notice the problem only has two layers of dependencies. Mod 2 to the access index.

Variant Code

public int backPack(int K, int[] items) {
   // sanity check
   if (K < 0 || items == null) {
       return -1;
   }
   // create memo table
   int n = items.length;
   boolean[][] KP = new boolean[2][K+1];
   // init base cases
   KP[0][0] = true;
   // topo order
   for (int i = 1; i <= n; i++) {
       for (int k = 0; k <= K; k++) {
          int ri = i - 1;
          KP[i%2][k] = KP[(i-1)%2][k];
          if (k - items[ri] >= 0) {
               KP[i%2][k] = KP[i%2][k] || KP[(i-1)%2][k-items[ri]];
          }
       }
   }
   // find the largest k
   for (int k = K; k > 0; k--) {
       if (KP[n%2][k]) return k;
   }
   return 0;
}

Time & Space Complexity

Time O(nK) Space O(K)

Variant II (LC.416)

Given an integer array (non-negative), determine if the array can be partitioned into two subsets with equal sum.

This question can framed as the possibility of a tie situation in presidential election given the votes in electoral college.

Example

I: [1, 5, 11, 5]
O: True Set 1 [1,5,5] Set 2 [11]
I: [1, 2, 3, 5]
O: False no way to equally partition the set

Brute Force Approach

Because of the nature of a subset, we can get the rest of the items (the other subset) for free. We can first divide the target sum in half, then try all subsets to see if one can sum to target/2. Like any other exhaustive search, it will have an exponential running time.

Optimization

First step is to define a representation of the problem.

Code

public boolean canPartition(int[] nums) {
   int sum = 0;
   for (int num : nums) {
       sum += num;
   }

   if(sum % 2 == 1){
       return false;
   } else {
       return backpack1(sum / 2, nums);
   }
}