背包问题

背包类问题的特点
预览
- Backpack
分析
Code
- 分裂成两个和相等的子集（背包1的变种问题）
Straightforward thoughts
动态规划做法
- Backpack 2
分析
Code
- K Sum
Question
分析
Code
- Minimum Adjustment Cost
Idea
- 416. Partition Equal Subset Sum
- 494.Target Sum

背包类问题的特点

用值作为DP的维度 (枚举每一种值可能出现的情况)
DP过程就是填写矩阵
可以滚动数组优化

预览

问题：n个物品，每个物品体积为A[i],价值为V[i]，一个背包的容量为m，这个背包能放多少价值。

思路：最后一个物品放不放？

f[i][j] = max(f[i- 1][j], f[i - 1][j - A[i]] + V[i]) 状态方程定义：前i个物品放在容量为j的包里面，最多能放多少价值。

背包三：如果每个物品都可以放无数次，能放多少价值？ f[i][j] = max(f[i- 1][j], f[i][j - A[i]] + V[i])

最优化问题转化为计数问题，就是把Max换成加号。问：有多少种方法可以把背包装满。初始化f[0][0] = 1

Backpack

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.

分析

State: dp[n][s] 前n项个物品，能否充满体积为s的背包

Function: 对于当前的物品，有两个状态，取或者不取 dp[i][s] = dp[i - 1][s] || dp[i - 1][s - a[i - 1]]

Init: dp[0] false; dp[i][0] true

Answer: dp[n] 最大

可以滚动数组优化

Code

public class Solution {
    public int backPack(int m, int[] A) {
        // write your code here
        if(A == null || A.length == 0) {
            return 0;
        }
        int n = A.length;

        boolean[][] dp = new boolean[n + 1][m + 1];
        dp[0][0] = true;

        for(int i = 1; i <= n; i++) {
            for(int j = 0; j <= m; j++) {
                // 不取当前物品
                if(dp[i - 1][j]) {
                    dp[i][j] = true;
                // 取当前物品
                } else if (j >= A[i - 1] && dp[i - 1][j - A[i - 1]]) {
                    dp[i][j] = true;
                }
            }
        }
        // 因为size和物品的体积无关，所以可能第一个物品就充满了，之后怎么也不能放了
        for(int i = m; i >= 0; i--) {
            if(dp[n][i]) {
                return i;
            }
        }
        return 0;        
    }
}

滚动数组优化

public class Solution {
    public int backPack(int m, int[] A) {
        // write your code here
        if(A == null || A.length == 0) {
            return 0;
        }
        int n = A.length;

        boolean[][] dp = new boolean[2][m + 1];
        dp[0][0] = true;

        for(int i = 1; i <= n; i++) {
            for(int j = 0; j <= m; j++) {
                if(dp[(i - 1) % 2][j]) {
                    dp[i % 2][j] = true;
                } else if (j >= A[i - 1] && dp[(i - 1) % 2][j - A[i - 1]]) {
                    dp[i % 2][j] = true;
                }
            }
        }

        for(int i = m; i >= 0; i--) {
            if(dp[n % 2][i]) {
                return i;
            }
        }

        return 0;       
    }
}

分裂成两个和相等的子集（背包1的变种问题）

给定一个只包含正整数的非空数组，判断该数组是否能分裂成两个和相等的子数组

输入[1,5,11,5]，返回 true . 可以分为[1,5,5]和[11]

“数组能否分为两个和想等的子数组” 等价于 “在数组中选取一定数目的元素，能否使得选择的元素之和为sum/2(sum为数组中所有元素的和)”

等价的问题就是经典的0-1背包问题，即给定一个正整数数组，能否从数组中选取一定数量的元素，使得这些元素的和恰好为sum/2。

Straightforward thoughts

枚举原数组的所有子集计算每个子集的元素之和能否等于sum/2 但是含有n个元素的数组的子集数目为2^n个

动态规划做法

子问题是什么？

假设数组中存在子集num1,num2,...,numk满足和为sum/2,那么，从该子集中去掉最后一个元素numk,其和一定为sum/2-numk。

子问题是：是否存在一个子集，其和为sum/2-numk,

dp[i][j] 表示数组中的前i个元素能否得到和为j的子数组

对于每个元素，有两种可能放还是不放？放的话：前i - 1个元素的和就是j - nums[i]; 不放的话：前i - 1个元素的和就是j

dp[i][j] = dp[i - 1][j - nums[i]] || dp[i - 1][j] 可以滚动数组优化

public boolean canGetTwoArray(int[] nums) {
    if(nums == null || nums.length == 0 ) {
        return false;
    }

    int sum = 0;
    for(int num : nums) {
        sum += num;
    }
    // 易错点
    if(sum % 2 == 1) {
        return false;
    }

    boolean[][] dp = new boolean[2][sum/2 + 1];
    dp[0][0] = true;

    for(int i = 1; i <= nums.length; i++) {
        for(int j = 0; j <=  sum / 2; j++) {
            if(dp[(i - 1) % 2][j]) {
                dp[i % 2][j] = true;
            } else if(j >= nums[i - 1]) {
                dp[i % 2][j] = dp[(i - 1) % 2][j - nums[i]];
            }
        }
    }

    return dp[nums.length % 2][sum / 2];

}

Backpack 2

如果每个物品的价值不统一，怎么能取得最大的价值。

硬币凑整

Given n items with size Ai and value Vi, and a backpack with size m. What's the maximum value can you put into the backpack?

Example Given 4 items with size [2, 3, 5, 7] and value [1, 5, 2, 4], and a backpack with size 10. The maximum value is 9.

分析

贪心的做法，取单位体积价值更大的。但是这样会造成空余的空间没法使用，

State: dp[i][j] 表示前i个物品中选择一些物品组成容量为j的最大价值是多少

Function: 对于当前的物品，有两个状态，取或者不取 dp[i][s] = max(dp[i - 1][s],dp[i - 1][s - A[i - 1]] + V[i - 1])

Init: dp[0][0] = 0

Answer: dp[n][s]

Code

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

        int n = A.length , i, j;
        for(i = 0; i < n; i++){
            for(j = m; j >= A[i]; j--){
                if (f[j] < f[j - A[i]] + V[i])
                    f[j] = f[j - A[i]] + V[i];
            }
        }
        return f[m];
    }
}

K Sum

Question

Given n distinct positive integers, integer k (k <= n) and a number target.

Find k numbers where sum is target. Calculate how many solutions there are?

Example: Given [1,2,3,4], k = 2, target = 5.

There are 2 solutions: [1,4] and [2,3].

Return 2.

分析

n, k, target 对于每一个数我们都有两种选择，选或者不选。类似于背包问题，我们把target的值也作为一个维度。

State: dp[i][j][t] 把target的值也作为一个维度前i个数里面，选j个数，组成的值为t的个数有多少。

Function: dp[i][j][t] = dp[i - 1][j][t] + dp[i - 1][j - 1][t - V[i - 1]]

Init: dp[i][0][0] = 1

Answer: dp[n][k][target]

Code

public int kSum(int A[], int k, int target) {
    // write your code here
    if(A == null || A.length == 0) {
        return 0;
    }
    int n = A.length;
    int[][][] dp = new int[n + 1][k + 1][target + 1];

    for(int i = 0; i <= n; i++) {
        dp[i][0][0] = 1;
    }

    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= k && j <= i; j++) {
            for(int t = 1; t <= target; t++) {
                if(t >= A[i - 1]) {
                    dp[i][j][t] = dp[i - 1][j - 1][t - A[i - 1]];
                }

                dp[i][j][t] += dp[i - 1][j][t];
            }
        }
    }

    return dp[n][k][target];

}

滚动数组降维优化

public int kSum(int A[], int k, int target) {
    // write your code here
    if(A == null || A.length == 0) {
        return 0;
    }
    int n = A.length;
    int[][][] dp = new int[2][k + 1][target + 1];   
    dp[0][0][0] = 1;

    for(int i = 1; i <= n; i++) {
        dp[i % 2][0][0] = 1;
        for(int j = 1; j <= k && j <= i; j++) {
            for(int t = 1; t <= target; t++) {
                // 需要清除之前残除的状态
                dp[i % 2][j][t] = 0;
                if(t >= A[i - 1]) {
                    dp[i % 2][j][t] = dp[(i - 1) % 2][j - 1][t - A[i - 1]];
                }
                dp[i % 2][j][t] += dp[(i - 1) % 2][j][t];
            }
        }
    }
    return dp[n % 2][k][target];   
}

Minimum Adjustment Cost

Given an integer array, adjust each integers so that the difference of every adjacent integers are not greater than a given number target.

If the array before adjustment is A, the array after adjustment is B, you should minimize the sum of |A[i]-B[i]|

You can assume each number in the array is a positive integer and not greater than 100.

Example Given [1,4,2,3] and target = 1, one of the solutions is [2,3,2,3], the adjustment cost is 2 and it's minimal.

Return 2.

Idea

State: dp[i][v] , 第i个数调整为V，满足相邻的两个数之差 <= target, 所需要的最小代价

Function: dp[i][v] = min(dp[i - 1][v'] + |A[i] - v|, |v - v'| <= target)

Init: dp = Max; // 求的是最小代价

Answer: f[n][A[n] - target ~ A[n] + target]

public int MinAdjustmentCost(ArrayList<Integer> A, int target) {
    // write your code here
    if(A == null || A.size() == 0) {
        return 0;
    }

    int n = A.size();
    int[][] dp = new int[n + 1][101];

    for (int i = 0; i <= n ; i++)
        for (int j = 0; j <=100; j++)
            dp[i][j] = Integer.MAX_VALUE;

    for(int i = 0; i <= 100; i++) {
        dp[0][i] = 0;
    }

    // 第i位和第i-1位都需要调整
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j <= 100; j++) {
            if(dp[i - 1][j] != Integer.MAX_VALUE) {
                for(int k = 0; k <= 100; k++) {
                    if(Math.abs(j - k) <= target) {
                        // 调整第i位的值到k, 使得第i位和第i-1位的值不大于target
                        dp[i][k] = Math.min(dp[i][k], dp[i - 1][j] + Math.abs(A.get(i - 1) - k));
                    }
                }
            }
        }
    }

    int result = Integer.MAX_VALUE;
    for(int i = 0; i <= 100; i++) {
        result = Math.min(result, dp[n][i]);
    }

    return result;
}

416. Partition Equal Subset Sum

问题是找到两个subset，其中每个subset的和都相同。

so this is a backpack question. What we need to do is to pick up elements of subsets which has a sum = allSum / 2.

public class Solution {
    public boolean canPartition(int[] nums) {
        if(nums == null || nums.length == 0) return false;

        int l = nums.length;
        int sum = 0;

        for(int n : nums) {
            sum += n;
        }

        if(sum % 2 != 0) return false;

        sum /= 2;

        boolean[] dp = new boolean[sum + 1];

        dp[0] = true;

        for(int i = 1; i <= l; i++) {
            for(int j = sum; j >= nums[i - 1]; j--) {
                dp[j] = dp[j] || dp[j - nums[i - 1]];
            }
        }

        return dp[sum];
    }
}

494.Target Sum

It's a good question. Because it can demonstrate why should we choose the backpack algorithm, how the backpack better than recursive solution.

The recursive solution is very slow, because its runtime is exponential.

Find a subset of nums, that need to be positive, and the rest of them negative, such that the sum is equal to target.

sum(P) + sum(N) + sum(P) - sum(N) = target + sum(P) + sum(N) =>

Find a subset P of nums such that sum(P) = (target + sum) / 2

public class Solution {
    public int findTargetSumWays(int[] nums, int S) {
        if(nums == null || nums.length == 0) return 0;

        int sum = 0;

        for(int n : nums) {
            sum += n;
        }

        // if the sum small than the target, it cannot be possible
        if(sum < S || (sum + S) % 2 != 0) return 0;

        return helper(nums, (sum + S) / 2);
    }

    private int helper(int[] nums, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;

        for(int n : nums) {
            for(int i = target; i >= n; i--) {
                dp[i] += dp[i - n];
            }
        }

        return dp[target];

    }
}

背包问题

背包问题

背包类问题的特点

预览

Backpack

分析

Code

分裂成两个和相等的子集（背包1的变种问题）

Straightforward thoughts

动态规划做法

Backpack 2

分析

Code

K Sum

Question

分析

Code

Minimum Adjustment Cost

Idea

416. Partition Equal Subset Sum

494.Target Sum

results matching ""

No results matching ""