Algorithms Series: 0/1 BackPack – Dynamic Programming and BackTracking

acm-association-computing-machinery

Given n items with size A[i] (i from 0 to n – 1), an integer m denotes the size of a backpack. How full you can fill this backpack?

Put this mathematically, you are trying to:

max(sum(j[i] * A[i]))
subject to: j[i] = {0, 1} and sum(j[i] * A[i]) <= m
where 0 =< i < n

j[i] indicates that whether you put item i in the backpack.

Backtracking

If we start from the first item, we have two choices, put it or do not put it in the bag. So it is a decision binary tree of depth n where each level corresponding to a item. The complexity is O(2^n) .

If the remaining capacity is enough (bigger than the current size of item), otherwise we can choose skipping current item.

class Solution {
public:
    /**
     * @param m: An integer m denotes the size of a backpack
     * @param A: Given n items with size A[i]
     * @return: The maximum size
     */
     
    int backPack(int m, vector<int> &A) {
        pack(0, m, A);
        return curMax;
    }

    void pack(int n, int weight, vector<int> &A) {
        int sz = A.size();
        int m = 0;
        for (int i = n; i < sz; i ++) {
            pack(n + 1, weight, A);  // do not put it
            if (weight >= A[i]) {   // we can put it
                m += A[i];
                if (m > curMax) {
                    curMax = m;
                }
                weight -= A[i];
                pack(n + 1, weight, A);  // put it
            } 
        }
    }
    
private:
    int curMax = 0;
};

However, this recursion backtracking is too slow because of the large search space especially if n is large.

Dynamic Programming

If, we use dp[i][j] to represent that if we can use first i items (maximum, could use less) to pack at most j weight. Thus, the following stands:

dp[i][j] = dp[i - 1][j] || dp[i - 1][j - A[i - 1]];

This can be interpreted as:

• by achieving dp[i][j] we automatically achieve dp[i + 1][j]
• by achieving dp[i][j] we automatically achieve dp[i + 1][j + A[i + 1]]

The Dynamic Programming solution allows you to cache intermediate results so you don’t have to calculate them over and over again.

class Solution {
public:
    /**
     * @param m: An integer m denotes the size of a backpack
     * @param A: Given n items with size A[i]
     * @return: The maximum size
     */
     
    int backPack(int m, vector<int> &A) {
            int size = A.size();
            vector< vector<bool> > dp(size + 1, vector<bool>(m + 1, false));
            for (int i = 0; i < size + 1; ++ i) {
                dp[i][0] = true;
            }
            for(int i = 1; i < A.size() + 1; i++) {
                for(int j = 1; j < m + 1; j++) {
                    if(j < A[i - 1]) { // insufficient capacity
                        dp[i][j] = dp[i - 1][j];
                    } else {
                        dp[i][j] = dp[i - 1][j] || dp[i - 1][j - A[i - 1]];
                    }
                }
            }
            for (int i = m; i >= 0; i--) { // reverse checking the maximum weight
                if (dp[size][i]) {
                    return i;
                }
            }
            return 0;
    }
};

The O(nm) solution (with O(mn) space) fills the DP array and in the end, we need to check if we can fulfil the backpack from m downards to zero (get the maximum)

DP Memory Optimisation

We can see that the dp[i] is fully dependent on the dp[i-1], thus, we can optimise the memory consumption from O(mn) to O(m).

class Solution {
public:
    /**
     * @param m: An integer m denotes the size of a backpack
     * @param A: Given n items with size A[i]
     * @return: The maximum size
     */
     
    int backPack(int m, vector<int> &A) {
            int size = A.size();
            vector<bool> dp(m + 1, false);
            dp[0] = true;
            for (int i = 1; i < A.size() + 1; i++) {
                for (int j = m; j >= 1; --j) {
                    if(j >= A[i - 1]) {
                        dp[j] = dp[j] || dp[j - A[i - 1]];
                    }
                }
            }
            for (int i = m; i >= 0; i--) {
                if (dp[i]) {
                    return i;
                }
            }
            return 0;
    }
};

The runtime complexity is still O(mn) where you need to reverse the inner loop from m downwards to 1.

Knapsack Problems

• Teaching Kids Programming - 0/1 Knapsack: Length of the Longest Subsequence That Sums to Target (Recursion+Memoization=Top Down Dynamic Programming)
• Teaching Kids Programming - 0/1 Knapsack Space Optimised Dynamic Programming Algorithm
• Teaching Kids Programming - Using Bottom Up Dynamic Programming Algorithm to Solve 0/1 Knapsack Problem
• Teaching Kids Programming - 0/1 Knapsack Problem via Top Down Dynamic Programming Algorithm
• Teaching Kids Programming - Multiple Strange Coin Flips/Toss Bottom Up Dynamic Programming Algorithm (Knapsack Variant)
• Teaching Kids Programming - Multiple Strange Coin Flips/Toss Top Down Dynamic Programming Algorithm (Knapsack Variant)
• Teaching Kids Programming - Max Profit of Rod Cutting (Unbounded Knapsack) via Bottom Up Dynamic Programming Algorithm
• Teaching Kids Programming - Max Profit of Rod Cutting (Unbounded Knapsack) via Top Down Dynamic Programming Algorithm
• Teaching Kids Programming - Brick Layout (Unlimited Knapsack) via Bottom Up Dynamic Programming Algorithm
• Teaching Kids Programming - Brick Layout (Unlimited Knapsack) via Top Down Dynamic Programming Algorithm
• Count Multiset Sum (Knapsacks) by Dynamic Programming Algorithm
• Count Multiset Sum (Knapsacks) by Recursive BackTracking Algorithm
• Dynamic Programming Algorithm to Solve the Poly Knapsack (Ubounded) Problem
• Dynamic Programming Algorithm to Solve 0-1 Knapsack Problem
• Classic Unlimited Knapsack Problem Variant: Coin Change via Dynamic Programming and Depth First Search Algorithm
• Classic Knapsack Problem Variant: Coin Change via Dynamic Programming and Breadth First Search Algorithm
• Complete Knapsack Problem
• 0/1 Knapsack Problem
• Teaching Kids Programming - Combination Sum Up to Target (Unique Numbers) by Dynamic Programming Algorithms
• Algorithms Series: 0/1 BackPack - Dynamic Programming and BackTracking
• Using BackTracking Algorithm to Find the Combination Integer Sum
• Facing Heads Probabilties of Tossing Strange Coins using Dynamic Programming Algorithm
• Partition Equal Subset Sum Algorithms using DFS, Top-Down and Bottom-up DP

–EOF (The Ultimate Computing & Technology Blog) —