Backpack I&II

BackPack I

– different sizes same price, ask maximum solution with fixed bag size

Given n items with size Ai, an integer m denotes the size of a backpack. How full you can fill this backpack?

 Example

If we have 4 items with size [2, 3, 5, 7], the backpack size is 11, we can select [2, 3, 5], so that the max size we can fill this backpack is 10. If the backpack size is 12. we can select [2, 3, 7] so that we can fulfill the backpack.

You function should return the max size we can fill in the given backpack.

Note

You can not divide any item into small pieces.

Challenge

O(n x m) time and O(m) memory.

O(n x m) memory is also acceptable if you do not know how to optimize memory.

 

Solution 1: DP – O(nm) time and O(nm) memory

state: f[i][j] = “前i”个数,取出一些组成和为<=j的最大值

function: f[i][j] = f[i-1][j – a[i]] + a[i] //取a[i]的情况

o f[i-1][j] //不取a[i]的情况

两种情况取max

public int backPack(int m, int[] A) {
    if (m <= 0 || A == null || A.length == 0) {
        return 0;
    }
    int[][] backPack = new int[A.length + 1][m + 1];
    for (int i = 0; i <= A.length; i++) {
        backPack[i][0] = 0;
    }
    for (int j = 0; j <= m; j++) {
        backPack[0][j] = 0;
    }
    int max = 0;
    for (int i = 1; i <= A.length; i++) {
        for (int j = 1; j <= m; j++) {
            //doesn't contain A[i]
            backPack[i][j] = backPack[i - 1][j];
            //contains A[i]
            if (j >= A[i - 1]) {
                backPack[i][j] = Math.max(backPack[i][j], backPack[i - 1][j - A[i - 1]] + A[i - 1]);
            }
            if (backPack[i][j] > max) {
                max = backPack[i][j];
            }
        }
    }
    return max;
}

Solution 2. O(mn) time O(n) space, 利用行数取模优化空间 rolling array

public int backPack(int m, int[] A) {
    if (m <= 0 || A == null || A.length == 0) {
        return 0;
    }
    int[][] backPack = new int[2][m + 1];
    for (int i = 0; i < 2; i++) {
        backPack[i][0] = 0;
    }
    for (int j = 0; j <= m; j++) {
        backPack[0][j] = 0;
    }
    int max = 0;
    for (int i = 1; i <= A.length; i++) {
        for (int j = 1; j <= m; j++) {
            //doesn't contain A[i]
            backPack[i % 2][j] = backPack[(i - 1) % 2][j];
            //contains A[i]
            if (j >= A[i - 1]) {
                backPack[i % 2][j] = Math.max(backPack[i % 2][j], backPack[(i - 1) % 2][j - A[i - 1]] + A[i - 1]);
            }
            if (backPack[i % 2][j] > max) {
                max = backPack[i % 2][j];
            }
        }
    }
    return max;
}

Solution 3: dp

f[i][j] = 前i个item能不能正好组成j

f[i][j] = f[i-1][j-a[i]] //取a[i]

f[i-1][j] //不取a[i]

两者取或

return max j which f[i][j] == true

public int backPack(int m, int[] A) {
    if (m <= 0 || A == null || A.length == 0) {
        return 0;
    }
    boolean[][] backPack = new boolean[A.length + 1][m + 1];
    backPack[0][0] = true;
    for (int i = 1; i <= A.length; i++) {
        backPack[i][0] = true;
    }
    for (int j = 1; j <= m; j++) {
        backPack[0][j] = false;
    }
    int max = 0;
    for (int i = 1; i <= A.length; i++) {
        for (int j = 1; j <= m; j++) {
            backPack[i][j] = backPack[i - 1][j];
            if (j >= A[i - 1]) {
                backPack[i][j] |= backPack[i - 1][j - A[i - 1]];
            }
            if (backPack[i][j]) {
                max = j;
            }
        }
    }
    return max;
}

BackPack II

– different size and price, ask for maximum value with fixed bag size

Solution 1. O(m*n) time, O(m*n) space

f[i][j]:maximum value with first i items in A with a m sized bag

f[i][j] = f[i-1][j – a[i]] + v[i] //取a[i]的情况

= f[i-1][j] //不取a[i]的情况

两者取max, return f[n][m]

public int backPackII(int m, int[] A, int V[]) {
    if (A == null || V == null || m <= 0) {
        return 0;
    }
    int[][] maxValue = new int[A.length + 1][m + 1];
    for (int i = 0; i <= A.length; i++) {
        maxValue[i][0] = 0;
    }
    for (int j = 0; j <= m; j++) {
        maxValue[0][j] = 0;
    }
    for (int i = 1; i <= A.length; i++) {
        for (int j = 1; j <= m; j++) {
            maxValue[i][j] = maxValue[i - 1][j];
            if (j >= A[i - 1]) {
                maxValue[i][j] = Math.max(maxValue[i][j], maxValue[i - 1][j - A[i - 1]] + V[i - 1]);
            }
        }
    }
    return maxValue[A.length][m];
}

Solution 2: O(m*n) time, O(m) space

利用rolling array 进行优化

public int backPackII(int m, int[] A, int V[]) {
    if (A == null || V == null || m <= 0) {
        return 0;
    }
    int[][] maxValue = new int[2][m + 1];
    for (int i = 0; i < 2; i++) {
        maxValue[i][0] = 0;
    }
    for (int j = 0; j <= m; j++) {
        maxValue[0][j] = 0;
    }
    for (int i = 1; i <= A.length; i++) {
        for (int j = 1; j <= m; j++) {
            maxValue[i % 2][j] = maxValue[(i - 1) % 2][j];
            if (j >= A[i - 1]) {
                maxValue[i % 2][j] = Math.max(maxValue[i % 2][j], maxValue[(i - 1) % 2][j - A[i - 1]] + V[i - 1]);
            }
        }
    }
    return maxValue[A.length % 2][m];
}
FacebookTwitterGoogle+Share

Wildcard Matching

Implement wildcard pattern matching with support for '?' and '*'.

  • '?' Matches any single character.
  • '*' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

 Example
<code>isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false</code>

Solution1. Dynamic Programming

isMatch[i][j] = if first i chars for s can match first j chars of p

j==’*’: OR(isMatch[0~i][j-1])

j==’?’: isMatch[i-1][j-1]

else: isMatch[i-1][j-1] && s.charAt(i-1)==p.charAt(j-1)

public boolean isMatch(String s, String p) {
    //dp version
    if (s == null || p == null) {
        return false;
    }
    boolean[][] isMatch = new boolean[s.length() + 1][p.length() + 1];
    isMatch[0][0] = true;
    for (int i = 1; i <= s.length(); i++) {
        isMatch[i][0] = false;
    }
    for (int j = 1; j <= p.length(); j++) {
        isMatch[0][j] = isMatch[0][j - 1] && p.charAt(j - 1) == '*';
    }
    for (int i = 1; i <= s.length(); i++) {
        for (int j = 1; j <= p.length(); j++) {
            if (p.charAt(j - 1) == '*') {
                for (int k = 0; k <= i; k++) {
                    if (isMatch[k][j - 1]) {
                        isMatch[i][j] = true;
                        break;
                    }
                }
            } else if (p.charAt(j - 1) == '?') {
                isMatch[i][j] = isMatch[i - 1][j - 1];
            } else {
                isMatch[i][j] = isMatch[i - 1][j - 1] && s.charAt(i - 1) == p.charAt(j - 1);
            }
        }
    }
    return isMatch[s.length()][p.length()];
}

Interleaving String

Given three strings: s1, s2, s3, determine whether s3 is formed by the interleaving of s1 and s2.

Example

For s1 = "aabcc", s2 = "dbbca"

  • When s3 = "aadbbcbcac", return true.
  • When s3 = "aadbbbaccc", return false.

 

Solution: Dynamic Programming
isInterleave[i][j] = if first i chars of s1 and first j chars of s2 is interleave of first i+j chars of s3
isInterleave[i][j] = isInterleave[i – 1][j] && s1.charAt(i – 1) == s3.charAt(i + j – 1))
|| (isInterleave[i][j – 1] && s2.charAt(j – 1) == s3.charAt(i + j – 1))

public boolean isInterleave(String s1, String s2, String s3) {
    if (s1 == null || s2 == null || s3 == null
            || s1.length() + s2.length() != s3.length()) {
        return false;
    }
    //isInterleave[i][j] = if first i chars of s1 and first j chars of s2
    //is interleave of first i+j chars of s3
    boolean[][] isInterleave = new boolean[s1.length() + 1][s2.length() + 1];
    isInterleave[0][0] = true;
    for (int i = 1; i <= s1.length(); i++) {
        isInterleave[i][0] = isInterleave[i - 1][0] && s1.charAt(i - 1) == s3.charAt(i - 1);
    }
    for (int j = 1; j <= s2.length(); j++) {
        isInterleave[0][j] = isInterleave[0][j - 1] && s2.charAt(j - 1) == s3.charAt(j - 1);
    }
    for (int i = 1; i <= s1.length(); i++) {
        for (int j = 1; j <= s2.length(); j++) {
            isInterleave[i][j] = (isInterleave[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1))
                                 || (isInterleave[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1));
        }
    }
    return isInterleave[s1.length()][s2.length()];
}