能力随心，自然成长

0%

背包问题整理

发表于 更新于 分类于

整理了一下几种背包问题。

背包问题I

描述：在n个物品中挑选若干物品装入背包，最多能装多满？假设背包的大小为m，每个物品的大小为A[i]

1
public class backpack_1 {
2
    public int backPack_1(int m, int[] A) {
3
        if (A.length == 0 || m == 0) return 0;
4
        int[][] dp = new int[A.length + 1][m + 1]; //表示 当前选择第i个物品背包容量为j的情况
5
        for (int i = 1; i <= A.length; i++) { //遍历物品
6
            for (int j = 1; j <= m; j++) {
7
                if (j >= A[i - 1]) { //2种情况： 当前物品选和不选
8
                    dp[i][j] = Math.max(dp[i - 1][j], 
9
                                        dp[i - 1][j - A[i - 1]] + A[i - 1]);
10
                } else {
11
                    dp[i][j] = dp[i - 1][j];
12
                }
13
            }
14
        }
15
        return dp[A.length][m];
16
    }
17
18
    //二维变一维
19
    public int backPack_2(int m, int[] A) {
20
        if (A.length == 0 || m == 0) return 0;
21
        int[] dp = new int[m + 1];
22
23
        for (int i = 1; i <= A.length; i++) {
24
            for (int j = m; j >= 1; j--) { //这边需要倒序 因为dp[i-1][j-A[i-1]]不会被提前更新
25
                if (j >= A[i - 1]) {
26
                    dp[j] = Math.max(dp[j], dp[j - A[i - 1]] + A[i - 1]);
27
                }
28
            }
29
        }
30
        return dp[m];
31
    }
32
}

背包问题II（01背包）

描述：有 n 个物品和一个大小为 m 的背包. 给定数组 A 表示每个物品的大小和数组 V 表示每个物品的价值.

问最多能装入背包的总价值是多大?（每个物品只能取一次）

思路和上题一样，只需要修改一处即可。

1
public class backpack_2 {
2
    public int backPackII_1(int m, int[] A, int[] V) {
3
        if (m == 0 || A.length == 0 || V.length == 0) return 0;
4
        int[][] dp = new int[A.length + 1][m + 1];
5
        for (int i = 1; i <= A.length; i++) {
6
            for (int j = 1; j <= m; j++) {
7
                if (j >= A[i - 1]) {
8
                    dp[i][j] = Math.max(dp[i - 1][j], 
9
                                        dp[i - 1][j - A[i - 1]] + V[i - 1]);
10
                } else {
11
                    dp[i][j] = dp[i - 1][j];
12
                }
13
            }
14
        }
15
        return dp[A.length][m];
16
    }
17
18
    public int backPackII_2(int m, int[] A, int[] V) {
19
        if (m == 0 || A.length == 0 || V.length == 0) return 0;
20
        int[] dp = new int[m + 1];
21
        for (int i = 1; i <= A.length; i++) {
22
            for (int j = m; j >= 1; j--) {
23
                if (j >= A[i - 1]) {
24
                    dp[j] = Math.max(dp[j], dp[j - A[i - 1]] + V[i - 1]);
25
                }
26
            }
27
        }
28
        return dp[m];
29
    }
30
}

背包问题III（完全背包 求值）

描述：给定n种大小为A[i]，值为V[i]的物品(每个物品都有无限多的可用物品)和一个大小为m的背包，你能放入背包的最大值是多少?

1
public class backpack_3 {
2
    //思路：视为特殊的多重背包问题 每个物品的个数的最大为m/A[i]
3
    public int backPackIII_1(int m, int[] A, int[] V) {
4
        if (m == 0 || A.length == 0 || V.length == 0) return 0;
5
        int[][] dp = new int[A.length + 1][m + 1];
6
7
        for (int i = 1; i <= A.length; i++) {
8
            for (int j = A[i - 1]; j <= m; j++) {
9
                dp[i][j] = dp[i - 1][j]; //第i个不选
10
                for (int k = 1; k * A[i - 1] <= m; k++) {
11
                    if (j >= k * A[i - 1]) { //当前第i个情况不选(k=0) 或者选k个
12
                        dp[i][j] = Math.max(dp[i][j],
13
                                dp[i - 1][j - k * A[i - 1]] + k * V[i - 1]);
14
                    }
15
                }
16
            }
17
        }
18
        return dp[A.length][m];
19
    }
20
21
    //多重背包问题解完全背包问题的DP优化
22
    public int backPackIII_2(int m, int[] A, int[] V) {
23
        if (m == 0 || A.length == 0 || V.length == 0) return 0;
24
        int[] dp = new int[m + 1];
25
        for (int i = 1; i <= A.length; i++) {
26
            for (int k = 1; k * A[i - 1] <= m; k++) {  //遍历当前该元素的个数
27
                for (int j = m; j >= A[i - 1]; j--) {
28
                    //当前元素 不取 或者取1个
29
                    dp[j] = Math.max(dp[j], dp[j - A[i - 1]] + V[i - 1]);
30
                }
31
            }
32
        }
33
        return dp[m];
34
    }
35
36
37
    //另一种思路 同leetcode518 零钱兑换II
38
    public int backPackIII_3(int m, int[] A, int[] V) {
39
        if (m == 0 || A.length == 0 || V.length == 0) return 0;
40
        int[] dp = new int[m + 1];
41
        for (int i = 1; i <= A.length; i++) {
42
            for (int j = A[i - 1]; j <= m; j++) {
43
                //对于当前物品i，若j从小到大的话，很可能在j之前的j-A[i-1]时已经放过第i件物品了，
44
                // 在j时再放就是重复放入；若j从大到小，则j之前的所有情况都没有更新过，
45
                // 不可能放过第i件物品，所以不会重复放入。 //与第二题相反
46
                dp[j] = Math.max(dp[j], dp[j - A[i - 1]] + V[i - 1]);
47
            }
48
        }
49
        return dp[m];
50
    }
51
}

背包问题IV（完全背包 求方案）

描述： 给出 n 个物品, 以及一个数组, nums[i]代表第i个物品的大小, 保证大小均为正数并且没有重复, 正整数 target 表示背包的大小, 找到能填满背包的方案数。每一个物品可以使用无数次

零钱兑换II 

1
public class backpack_4 {
2
    //爬楼梯 零钱兑换II
3
    public static int backPackIV_1(int[] nums, int target) {
4
        if (target < 0) return 0;
5
        int[][] dp = new int[nums.length + 1][target + 1];
6
7
        for (int i = 0; i <= nums.length; i++) {
8
            dp[i][0] = 1; //target=0时,对于任意硬币来说 都可以不选  所以都为1
9
        }
10
11
        for (int i = 1; i <= nums.length; i++) {
12
            for (int j = 1; j <= target; j++) {
13
                dp[i][j] = dp[i - 1][j]; //当前元素不选
14
                if (j - nums[i - 1] >= 0) { //当前元素选
15
                    dp[i][j] += dp[i][j - nums[i - 1]];
16
                }
17
            }
18
        }
19
        return dp[nums.length][target];
20
    }
21
22
23
    public int backPackIV_2(int[] nums, int target) {
24
        if (target < 0) return 0;
25
        int[] dp = new int[target + 1];
26
        dp[0] = 1;
27
        for (int i = 1; i <= nums.length; i++) { //加入第i个元素
28
            for (int j = nums[i - 1]; j <= target; j++) {  //当前元素可能的组合个数
29
                dp[j] += dp[j - nums[i - 1]];
30
            }
31
        }
32
        return dp[target];
33
    }
34
}

背包问题V

描述： 给出 n 个物品, 以及一个数组, nums[i] 代表第i个物品的大小, 保证大小均为正数, 正整数 target 表示背包的大小, 找到能填满背包的方案数。每一个物品只能使用一次 

1
public class backpack_5 {
2
    public int backPackV_1(int[] nums, int target) {
3
        int[][] dp = new int[nums.length + 1][target + 1];
4
        for (int i = 0; i <= nums.length; i++) {
5
            dp[i][0] = 1;
6
        }
7
        for (int i = 1; i <= nums.length; i++) {
8
            for (int j = 1; j <= target; j++) {
9
                dp[i][j] = dp[i - 1][j]; //不选当前元素
10
                if (j >= nums[i - 1]) { //选当前元素
11
                    // 这边+的时i-1 表示 如果选当前元素 之前没选过
12
                    dp[i][j] += dp[i - 1][j - nums[i - 1]];
13
                }
14
            }
15
        }
16
        return dp[nums.length][target];
17
    }
18
19
    public int backPackV_2(int[] nums, int target) {
20
        int[] dp = new int[target + 1];
21
        dp[0] = 1; // 目标为0  当前元素也不选
22
        for (int i = 1; i <= nums.length; i++) {
23
            for (int j = target; j >= nums[i - 1]; j--) {
24
                dp[j] += dp[j - nums[i - 1]];
25
            }
26
        }
27
        return dp[target];
28
    }
29
}

背包问题VI（组合问题）

描述： 给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。

顺序不同的序列被视作不同的组合。

注意与问题IV的区别：组合考虑元素之间的顺序

组合总和IV

1
public class combinationSum4_377 {
2
    //把该问题看成完全背包问题 并且考虑顺序 所以target循环放在外部
3
    //转移方程：dp[i] = dp[i]+dp[i-num]  i为目标数
4
    /**
5
     * 状态转移方程：dp[i]= dp[i - nums[0]] + dp[i - nums[1]] + dp[i - nums[2]] + ... （当 [] 		里面的数 >= 0）
6
     * 特别注意：dp[0] = 1，表示，如果那个硬币的面值刚刚好等于需要凑出的价值，这个就成为 1 种组合方案
7
     * 再举一个具体的例子：nums=[1, 3, 4], target=7;
8
     * dp[7] = dp[6] + dp[4] + dp[3]
9
     * 即：7 的组合数可以由三部分组成，1 和 dp[6]，3 和 dp[4], 4 和dp[3];
10
     */
11
    public int combinationSum4(int[] nums, int target) {
12
        int[] dp = new int[target + 1];
13
        dp[0] = 1;
14
        for (int i = 1; i <= target; i++) {
15
            for (int num : nums) {
16
                if (i >= num) {
17
                    dp[i] += dp[i - num];
18
                }
19
            }
20
        }
21
        return dp[target];
22
    }
23
}

多重背包问题

描述：给定n种大小为 A[i]，值为 V[i]的物品，每个物品有 amount[i] 个可用，一个大小为 m 的背包，你能放入背包的最大值是多少?

1
public class backpack_7 {
2
    public static int backpackVII_1(int[] A, int[] V, int[] amount, int m) {
3
        int[][] dp = new int[A.length + 1][m + 1];
4
        for (int i = 1; i <= A.length; i++) {
5
            for (int j = 1; j <= m; j++) {
6
                //dp[i][j] = dp[i - 1][j];
7
                for (int k = 0; k <= amount[i - 1]; k++) {
8
                    //k=0 表示当前元素不选
9
                    if (j >= k * A[i - 1]) {
10
                        dp[i][j] = Math.max(dp[i][j], 
11
                                            dp[i - 1][j - k * A[i - 1]] + k * V[i - 1]);
12
                    }
13
                }
14
            }
15
        }
16
        return dp[A.length][m];
17
    }
18
19
    public static int backpackVII_2(int[] A, int[] V, int[] amount, int m) {
20
        int[] dp = new int[m + 1];
21
        for (int i = 1; i <= A.length; i++) {
22
            for (int j = m; j >= A[i - 1]; j--) {
23
                for (int k = 1; k <= amount[i - 1]; k++) {
24
                    if (j >= k * A[i - 1]) {
25
                        dp[j] = Math.max(dp[j], dp[j - k * A[i - 1]] + k * V[i - 1]);
26
                    }
27
                }
28
            }
29
        }
30
31
        return dp[m];
32
    }
33
}

多重背包问题变种

描述：给出一些不同价值和数量的硬币。 找出这些硬币可以组合在1〜n范围内的多少个值

1
public class backpack_8 {
2
    //这种解法会超时
3
    public static int backpackVIII_1(int n, int[] V, int[] amount) {
4
        boolean[] dp = new boolean[n + 1];
5
        //状态转移：dp[j] = dp[j]||dp[i-V[i]]
6
        dp[0] = true;
7
        for (int i = 1; i <= V.length; i++) {
8
            for (int k = 1; k <= amount[i - 1]; k++) {
9
                for (int j = n; j >= V[i - 1]; j--) {
10
                    //dp[j] = dp[j] || dp[j - V[i - 1]];
11
                    if (!dp[j] && dp[j - V[i - 1]]) { //剪枝
12
                        dp[j] = true;
13
                    }
14
                }
15
            }
16
        }
17
        int ans = 0;
18
        for (int i = 1; i <= dp.length - 1; i++) {
19
            System.out.println(dp[i]);
20
            if (dp[i]) ans++;
21
        }
22
        return ans;
23
    }
24
25
    //优化 比较难想到
26
    public static int backpackVIII_2(int n, int[] V, int[] amount) {
27
        boolean[] dp = new boolean[n + 1];
28
        dp[0] = true;
29
        for (int i = 1; i <= V.length; i++) {
30
            int[] count = new int[n + 1];
31
            //count数组的含义  相同价值硬币的使用次数
32
            //count[x]即当前i的时候，多少个硬币i已经用了来和其他硬币凑出x的价值。
33
            for (int j = V[i - 1]; j <= n; j++) {
34
                //为什么正序遍历？
35
                /* 3种剪枝情况
36
                1. dp[j]已经为true 无须继续更新
37
                2. 加入当前[value]为true，需要保证[j-value]也为true
38
                3. 硬币使用数量受限
39
                * */
40
                if (!dp[j] && dp[j - V[i - 1]] && count[j - V[i - 1]] < amount[i - 1]) {
41
                    dp[j] = true;
42
                    count[j] = count[j - V[i - 1]] + 1;
43
                }
44
            }
45
        }
46
        int ans = 0;
47
        for (int i = 1; i <= dp.length - 1; i++) {
48
            System.out.println(dp[i]);
49
            if (dp[i]) ans++;
50
        }
51
        return ans;
52
    }
53
}

背包问题IX（01背包问题）

描述：你总共有n 万元，希望申请国外的大学，要申请的话需要交一定的申请费用，给出每个大学的申请费用以及你得到这个大学offer的成功概率，大学的数量是 m。如果经济条件允许，你可以申请多所大学。找到获得至少一份工作的最高可能性。0<=n<=10000,0<=m<=10000

样例：

1
样例 1:
2
	输入:  
3
		n = 10
4
		prices = [4,4,5]
5
		probability = [0.1,0.2,0.3]
6
	输出:  0.440
7
	解释：
8
	选择第2和第3个学校。
9
10
样例 2:
11
	输入: 
12
		n = 10
13
		prices = [4,5,6]
14
		probability = [0.1,0.2,0.3]
15
	输出:  0.370
16
	解释:
17
	选择第1和第3个学校。
1
public class backpack_9 {
2
    /**
3
     * 代码思路
4
     * 1. 定义一个二维数组dp[i]来表示花费i万元申请学校一所都没录取的概率
5
     * 2. 初始化dp数组，先假设录取概率都为0
6
     * 3. 操作probability数组，变成未录取的概率 probability[i] = 1.0 - probability[i]
7
     * 4. 第一层循环枚举i表示申请前i个学校
8
     * 5. 第二层循环枚举j表示花费j万元
9
     * 6. 根据算法思路中的状态转移方程来实现 dp[j] = min(dp[j],dp[j-prices[i]] * probability[i])
10
     * 7. dp[n]表示花费 n 万元一所学校都未录取的最小概率
11
     */
12
    //转换成01背包来想： 有n个学校，每个学校都不录取的值为Vi，求一所学校都没录取的最小值
13
    public static double backpackIX_1(int n, int[] prices, double[] probability) {
14
        double[][] dp = new double[prices.length + 1][n + 1];
15
        for (int i = 0; i <= prices.length; i++) {
16
            for (int j = 0; j <= n; j++) {
17
                dp[i][j] = 1.0;  //初始化
18
            }
19
        }
20
        for (int i = 0; i < probability.length; i++) {
21
            probability[i] = 1.0 - probability[i];
22
        }
23
        for (int i = 1; i <= prices.length; i++) {
24
            for (int j = 1; j <= n; j++) {
25
                if (j >= prices[i - 1]) { //选择当前学校
26
                    dp[i][j] = Math.min(dp[i - 1][j],
27
                            dp[i - 1][j - prices[i - 1]] * probability[i - 1]);
28
                } else {
29
                    dp[i][j] = dp[i - 1][j];
30
                }
31
            }
32
        }
33
        return 1 - dp[prices.length][n];
34
    }
35
36
    public static double backpackIX_2(int n, int[] prices, double[] probability) {
37
        double[] dp = new double[n + 1];
38
        for (int i = 0; i <= n; i++) {
39
            dp[i] = 1.0;
40
        }
41
        for (int i = 0; i < probability.length; i++) {
42
            probability[i] = 1.0 - probability[i];
43
        }
44
        for (int i = 1; i <= prices.length; i++) {
45
            for (int j = n; j >= prices[i - 1]; j--) {
46
                dp[j] = Math.min(dp[j], dp[j - prices[i - 1]] * probability[i - 1]);
47
            }
48
        }
49
        return 1 - dp[n];
50
    }
51
52
53
    public static void main(String[] args) {
54
        int n = 6595;
55
        int[] prices = new int[]{178, 4933, 9772, 4890, 1732, 1690, 3793};
56
        double[] weight = new double[]{0.1, 0.8, 0.8, 0.1, 0.2, 0.2, 0.8};
57
        System.out.println(backpackIX_1(n, prices, weight));
58
    }
59
}