背包问题(使用Java实现)

01背包问题

46. 携带研究材料（第六期模拟笔试） (kamacoder.com)

时间限制：5.000S  空间限制：128MB

题目描述

小明是一位科学家，他需要参加一场重要的国际科学大会，以展示自己的最新研究成果。他需要带一些研究材料，但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等，它们各自占据不同的空间，并且具有不同的价值。

小明的行李空间为 N，问小明应该如何抉择，才能携带最大价值的研究材料，每种研究材料只能选择一次，并且只有选与不选两种选择，不能进行切割。

输入描述

第一行包含两个正整数，第一个整数 M 代表研究材料的种类，第二个正整数 N，代表小明的行李空间。

第二行包含 M 个正整数，代表每种研究材料的所占空间。

第三行包含 M 个正整数，代表每种研究材料的价值。

输出描述

输出一个整数，代表小明能够携带的研究材料的最大价值。

输入示例

1
2
3
6 1
2 2 3 1 5 2
2 3 1 5 4 3

输出示例

1
5

提示信息

小明能够携带 6 种研究材料，但是行李空间只有 1，而占用空间为 1 的研究材料价值为 5，所以最终答案输出 5。

数据范围：
1 <= N <= 5000
1 <= M <= 5000
研究材料占用空间和价值都小于等于 1000

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
import java.io.*;

public class Main {
	static StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
	static int nextInt() throws IOException {
		st.nextToken();
		return (int) st.nval;
	}
	public static void main(String[] args) throws IOException {
		int M = nextInt();
		int N = nextInt();
		int[] space = new int[M+1];
		int[] value = new int[M+1];
		for(int i=1; i<=M; i++)
			space[i] = nextInt();
		for(int i=1; i<=M; i++)
			value[i] = nextInt();
		int[][] dp = new int[M+1][N+1];
		for(int i=1; i<=M; i++) {
			for(int j=1; j<=N; j++) {
				if(j<space[i]) {
					dp[i][j] = dp[i-1][j];
				}else {
					dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-space[i]]+value[i]);
				}
			}
		}
		out.printf("%d",dp[M][N]);
		out.flush();
	}
}

经过观察, 不难发现, 其实不需要二维数组, 每次外层循环内部, 都只操作一行, 那么就可以只用一行来模拟很多行, 也就是滚动数组

用一行模拟二维数组时, 应该向后还是向前遍历呢? 不难发现, 每一行取最大值时候, 需要访问前面的数据, 所以应该从后往前遍历, 就不会污染前面的数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import java.io.*;

public class Main {
	static StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
	static int nextInt() throws IOException {
		st.nextToken();
		return (int) st.nval;
	}
	public static void main(String[] args) throws IOException {
		int M = nextInt();
		int N = nextInt();
		int[] space = new int[M+1];
		int[] value = new int[M+1];
		for(int i=1; i<=M; i++)
			space[i] = nextInt();
		for(int i=1; i<=M; i++)
			value[i] = nextInt();
		int[] dp = new int[N+1];
		for(int i=1; i<=M; i++) {
			for(int j=N; j>=space[i]; j--) {
				dp[j] = Math.max(dp[j],dp[j-space[i]]+value[i]);
			}
		}
		out.printf("%d",dp[N]);
		out.flush();
	}
}

分割等和子集

416. 分割等和子集 - 力扣（LeetCode）

题目描述

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

示例 1：

输入： nums = [1,5,11,5]
输出： true
解释： 数组可以分割成 [1, 5, 5] 和 [11] 。

示例 2：

输入： nums = [1,2,3,5]
输出： false
解释： 数组不能分割成两个元素和相等的子集。

提示：

  • 1 <= nums.length <= 200
  • 1 <= nums[i] <= 100

这道题是经典的将问题转化为背包问题的思维模式

试想一下, 如果所有数的和是sum, 那么假设有一个背包, 它的最大承重量为sum/2, 那么此时如果把问题看成01背包问题的话, 就是从所有物品(数字)中取出最大价值(数字本身就是价值)的物品, 如果最大价值就是占满背包sum/2的话, 说明存在一种方案可以使得数组等分为两个等和的子集, 也就解决了问题

特殊的, 如果求和之后发现是奇数, 那么无论如何都不可能分割为两个等和子集, 所以这种情况可以直接返回, 无需使用01背包判断

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public boolean canPartition(int[] nums) {
        int n = nums.length;
        int sum = 0;
        for(int i=0; i<n; i++)
            sum+=nums[i];
        if((sum&1)==1)
            return false;
        int m = sum/2;
        int[] dp = new int[m+1];
        for(int i=0; i<n; i++){
            for(int j=m; j>=nums[i]; j--){
                dp[j] = Math.max(dp[j],dp[j-nums[i]]+nums[i]);
            }
        }
        return dp[m]==m;
    }
}

1049.最后一块石头的重量II

1049. 最后一块石头的重量 II - 力扣（LeetCode）

题目描述

有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。

每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

  • 如果 x == y，那么两块石头都会被完全粉碎；

  • 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。

最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。

示例 1：

输入： stones = [2,7,4,1,8,1]
输出： 1
解释：
组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]，
组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]，
组合 2 和 1，得到 1，所以数组转化为 [1,1,1]，
组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。

示例 2：

输入： stones = [31,26,33,21,40]
输出： 5

提示：

  • 1 <= stones.length <= 30
  • 1 <= stones[i] <= 100

虽然无法搞清楚究竟怎样的碰撞方案最优, 但是总体来看, 把石头分成近可能相近的两堆, 最后的差一定是最优方案

那么这时候就像上一道题那样, 直接sum/2的背包大小, 最后就可以得出最接近sum/2的一种组合方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        int n = stones.length;
        for(int i:stones)
            sum+=i;
        int m = sum/2;
        int[] dp = new int[m+1];
        for(int i=0; i<n; i++)
            for(int j=m; j>=stones[i]; j--)
                dp[j] = Math.max(dp[j],dp[j-stones[i]]+stones[i]);
        return sum-(dp[m]*2);
    }
}

494.目标和

494. 目标和 - 力扣（LeetCode）

题目描述

给你一个非负整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：

例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。

返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

示例 1：

输入： nums = [1,1,1,1,1], target = 3
输出： 5
解释： 一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

示例 2：

输入： nums = [1], target = 1
输出： 1

提示：

  • 1 <= nums.length <= 20
  • 0 <= nums[i] <= 1000
  • 0 <= sum(nums[i]) <= 1000
  • -1000 <= target <= 1000

注意题目并没有问是否可行, 而是问方法数, 也就是即使要转化为背包问题, 也不是要求一个大小为m的背包最大装的重量满不满足要求, 而是要记录方法数

也就是说dp[]内存的必须是方法数, 如果要满足题意, 必须找到一个分割方法, 使得sum=sum1+sum2, 其中sum1-sum2=target, 也就是(sum-target)/2=sum2, 我们要寻找组成sum2有多少种方法, 其中, 如果(sum-target)是奇数, 那么不符合要求, 如果是负数, 也不符合要求, 如果是0, 那么全是"+"即可符合要求

现在探讨大小为sum2的背包怎么存方法数

假设dp[j]表示存满大小为j的背包有多少种方法, 那么在第i行的情况如下, 没有物体i, 本身就有dp[j]种方法存满, 在第i行时, 需要探讨新的物品是否可以增加方法数, dp[j]+=dp[j-num[i]], 就是书包容量为j-num[i]的时候装满的方法数, 这些方法都可以加上一个num[i]使得书包装满j

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int n = nums.length;
        int sum = 0;
        for(int i:nums)
            sum+=i;
        if(((sum-target)&1)==1 || (sum-target)<0)
            return 0;
        int m = (sum-target)/2;
        int[] dp = new int[m+1];
        dp[0] = 1;
        for(int i=0; i<n; i++)
            for(int j=m; j>=nums[i]; j--)
                dp[j]+=dp[j-nums[i]];
        return dp[m];
    }
}

518. 零钱兑换 II(完全背包问题)

518. 零钱兑换 II - 力扣（LeetCode）

问题描述

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

假设每一种面额的硬币有无限个。

题目数据保证结果符合 32 位带符号整数。

示例 1：

输入： amount = 5, coins = [1, 2, 5]
输出： 4
解释： 有四种方式可以凑成总金额：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

示例 2：

输入： amount = 3, coins = [2]
输出： 0
解释： 只用面额 2 的硬币不能凑成总金额 3 。

示例 3：

输入： amount = 10, coins = [10]
输出： 1

提示：

  • 1 <= coins.length <= 300
  • 1 <= coins[i] <= 5000
  • coins 中的所有值 互不相同
  • 0 <= amount <= 5000

完全背包问题, 统计方法数不是是否可以装满背包, 此时只需要改变内层循环的遍历顺序, 从前往后遍历

之前01背包从后往前, 可以防止污染数据, 现在从前往后, 后面使用过物品也不影响后面继续使用

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int change(int amount, int[] coins) {
        int n = coins.length;
        int[] dp = new int[amount+1];
        dp[0] = 1;
        for(int i=0; i<n; i++)
            for(int j=coins[i]; j<=amount; j++)
                dp[j]+=dp[j-coins[i]];
        return dp[amount];
    }
}

377.组合总和 Ⅳ(排列问题, 题目要求顺序不同当成两种方案)

377. 组合总和 Ⅳ - 力扣（LeetCode）

题目描述

给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

题目数据保证答案符合 32 位整数范围。

示例 1：

输入： nums = [1,2,3], target = 4
输出： 7
解释：
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意，顺序不同的序列被视作不同的组合。

示例 2：

输入： nums = [9], target = 3
输出： 0

提示：

  • 1 <= nums.length <= 200
  • 1 <= nums[i] <= 1000
  • nums 中的所有元素 互不相同
  • 1 <= target <= 1000

既然是排列, 那就是所有顺序都可以看成不一样的情况, 看其来得用回溯法暴力搜索, 但是毕竟搜索时间复杂度太高, 我们再来看看能否用动态规划来解决

之前的动态规划都是外层遍历物品, 内层遍历背包容量, 意思是, 每增加一个物品, 都尝试不同的背包容量, 尝试用已有物品装满背包, 如果外层是背包容量, 内层是物品, 那么意思是, 每次增加一个单位的容量, 都一个一个增加物品种类来尝试装满它

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int combinationSum4(int[] nums, int target) {
        int n = nums.length;
        int[] dp = new int[target+1];
        dp[0] = 1;
        for(int i=1; i<=target; i++){
            for(int j=0; j<n; j++){
                if(nums[j]<=i){
                    dp[i]+=dp[i-nums[j]];
                }
            }
        }
        return dp[target];
    }
}

总结