2-7-2018 Knapsack problems

Backpack

本题是典型的01背包问题，每种类型的物品最多只能选择一件。参考前文Knapsack中总结的解法，这个题中可以将背包的 size 理解为传统背包中的重量；题目问的是能达到的最大 size, 故可将每个背包的 size 类比为传统背包中的价值。

考虑到数组索引从0开始，故定义状态bp[i + 1][j]为前i个物品中选出重量不超过j时总价值的最大值。状态转移方程则为分A[i] > j与否两种情况考虑。初始化均为0，相当于没有放任何物品。

public class Solution {
    /**
     * @param m: An integer m denotes the size of a backpack
     * @param A: Given n items with size A[i]
     * @return: The maximum size
     */
    public int backPack(int m, int[] A) {
        // write your code here
        boolean dp[][] = new boolean[A.length + 1][m + 1];
        for (int i = 0; i <= A.length; ++i) {
            dp[i][0] = true;
        }
        for (int i = 1; i <= A.length; ++i) {
            for (int j = 1; j <= m; ++j) {
                if (A[i - 1] > j) {
                    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) {
            if (dp[A.length][i]) {
                return i;
            }
        }
        return -1;
    }
}

Backpack 2 -> 0/1 Backpack(Knapsack without repetition)

when we have small dataset, we can just consider pick this element or not. At first, we need to check whether the current item can be select, in other words, if wt[i] > j, we cannot select the current item, so dp[i][j] = dp[i - 1][j]; otherwise, we can select the current item, next we should consider whether adding this item results in larger value. if include item[i], the value is dp[i - 1][j - A[i - 1]] + V[i - 1], if not include item[i], the value is dp[i - 1][j].

public class Solution {
    /*
     * @param m: An integer m denotes the size of a backpack
     * @param A: Given n items with size A[i]
     * @param V: Given n items with value V[i]
     * @return: The maximum value
     */
    public int backPackII(int m, int[] A, int[] V) {
        // write your code here
        int[][] dp = new int[A.length + 1][m + 1];
        boolean[][] helper = new boolean[A.length + 1][m + 1];

        for (int i = 1; i <= A.length; ++i) {
            for (int j = 1; j <= m; ++j) {
                if (j < A[i - 1]) {
                    // backpack cannot hold item i - 1
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - A[i - 1]] + V[i - 1]);
                    // pick item i and get value j
                    helper[i][j] = (dp[i - 1][j - A[i - 1]] + V[i - 1] > dp[i - 1][j]);
                }
            }
        }

        // determine which items to take
        boolean[] itemTake = new boolean[A.length];
        for (int i = A.length, j = m; i > 0; i--) {
            if (helper[i][j]) {
                itemTake[i - 1] = true;
                j -= A[i - 1];
            } else {
                itemTake[i - 1] = false;
            }
        }
        for (boolean flag : itemTake) {
            System.out.println("the items is picked ? " + flag);
        }

        return dp[A.length][m];
    }
}

follow up, how to get the specified item ? we can define one 2D helper array to record whether we select the ith item and get value j. then we use another 1D array to determine which items take.

Time: O(m * A.length)

refer to: 0/1 Knapsack Problem

think further, what if the m is very large ? 换一个维度来做

// 01 backpack with big datasets(O(n\sigma{v}), W is very big)
    public static int backpack2(int W, int[] w, int[] v) {
        int N = w.length;
        // sum of value array
        int V = 0;
        for (int i : v) {
            V += i;
        }
        // initialize
        int[][] dp = new int[N + 1][V + 1];
        for (int[] i : dp) {
            // should avoid overflow for dp[i][j - v[i]] + w[i]
            Arrays.fill(i, Integer.MAX_VALUE >> 1);
        }
        dp[0][0] = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j <= V; j++) {
                if (v[i] > j) {
                    // value[i] > j
                    dp[i + 1][j] = dp[i][j];
                } else {
                    // should avoid overflow for dp[i][j - v[i]] + w[i]
                    dp[i + 1][j] = Math.min(dp[i][j], dp[i][j - v[i]] + w[i]);
                }
            }
        }

        // search for the largest i dp[N][i] <= W
        for (int i = V; i >= 0; i--) {
            // if (dp[N][i] <= W) return i;
            if (dp[N][i] <= W) return i;
        }
        return 0;
    }

Backpack 2 -> Knapsack with repetition

the big difference between Knapsack with repetition and without repetition is that

令dp[i + 1][j]表示从前i种物品中选出总重量不超过j时总价值的最大值。那么有转移方程

dp[i + 1][j] = max{dp[i][j - k × w[i]] + k × v[i] | 0 ≤ k}
             = max{dp[i][j], max{dp[i][j - k × w[i]] + k × v[i] | 1 ≤ k}}
             = max{dp[i][j], dp[i + 1][j - w[i]] + v[j]}

注意等式最后一行，咋看和01背包一样，实际上区别在于dp[i + 1][], 01背包中为dp[i][].此时时间复杂度简化为O(nW)

    // repeated backpack
    public static int backpack3(int W, int[] w, int[] v) {
        int N = w.length;
        int[][] dp = new int[N + 1][W + 1];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j <= W; j++) {
                if (w[i] > j) {
                    // backpack cannot hold w[i]
                    dp[i + 1][j] = dp[i][j];
                } else {
                    dp[i + 1][j] = Math.max(dp[i][j], dp[i + 1][j - w[i]] + v[i]);
                }
            }
        }
        return dp[N][W];
    }