蓝桥杯备赛第二篇（背包问题）

1. 01 背包（采用状态压缩）

    public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int M = scanner.nextInt();int N = scanner.nextInt();int[] value = new int[N + 1];int[] weight = new int[N + 1];int[] dp = new int[M + 1];for (int i = 1; i <= N; i++) {weight[i] = scanner.nextInt();value[i] = scanner.nextInt();}for (int i = 1; i <= N; i++) {for (int j = M; j >= weight[i]; j--) {dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);}}System.out.println(dp[M]);}

2. 多重背包

	public static void main(String[] args) {Scanner scanner = new Scanner(System.in);//容量为Mint M = scanner.nextInt();//种类int N = scanner.nextInt();//价值int[] value = new int[N + 1];//占用体积int[] weight = new int[N + 1];//个数int[] num = new int[N + 1];for (int i = 1; i <= N; i++) {value[i] = scanner.nextInt();weight[i] = scanner.nextInt();num[i] = scanner.nextInt();}int[] dp = new int[M + 1];for (int i = 1; i <= N; i++) {for (int j = M; j >= weight[i]; j--) {for (int k = 0; k <= num[i] && k * weight[i] <= j; k++) {dp[j] = Math.max(dp[j], dp[j - k * weight[i]] + k * value[i]);}}}System.out.println(dp[M]);}

3. 完全背包

	public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int N = scanner.nextInt();int M = scanner.nextInt();int[] value = new int[N + 1];int[] weight = new int[N + 1];for (int i = 1; i <= N; i++) {value[i] = scanner.nextInt();weight[i] = scanner.nextInt();}int[] dp = new int[M + 1];for (int i = 1; i <= N; i++) {for (int j = weight[i]; j <= M; j++) {dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);}}}

4.二维背包

	public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int N = scanner.nextInt();int M = scanner.nextInt();int V = scanner.nextInt();int[] weight = new int[N + 1];int[] volume = new int[N + 1];int[] value = new int[N + 1];for (int i = 1; i <= N; i++) {weight[i] = scanner.nextInt();volume[i] = scanner.nextInt();value[i] = scanner.nextInt();}int[][] dp = new int[M + 1][V + 1];for (int i = 1; i <= N; i++) {for (int j = M; j >= weight[i]; j--) {for (int k = V; k >= volume[i]; k--) {dp[j][k] = Math.max(dp[j][k], dp[j - weight[i]][k - volume[i]] + value[i]);}}}System.out.println(dp[M][V]);}

5.例题1：子集和_可重复

求从一些不重复数字中选取一些数字使得和为target的方案数,每个数字可以重复使用,求方案数。这是一个完全背包问题。 

public static void main(String[] args) {int[] nums = new int[]{0, 1, 2, 3, 4, 5, 6,7,8,9,10};int target = 12;int N = 10;int[] dp = new int[target + 1];dp[0] = 1;for (int i = 1; i <= N; i++) {for (int j = nums[i]; j <= target; j++) {dp[j] += dp[j - nums[i]];}}System.out.println(dp[target]);}

 6.例题2：子集和_不可重复

求从一些不重复数字中选取一些数字使得和为target的方案数,每个数字最多只能选一次,求方案数。这是一个01问题。

public static void main(String[] args) {int[] nums = new int[]{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};int target = 12;int N = 10;int[] dp = new int[target + 1];dp[0] = 1;for (int i = 1; i <= N; i++) {for (int j = target; j >= nums[i]; j--) {dp[j] += dp[j - nums[i]];}}System.out.println(dp[target]);}

 7.例题3：2022

从1到2022个数中，选择10个数，求这10个数之和为2022的方案数。这是一个二维背包问题。

	public static void main(String[] args) {long[][] dp = new long[11][2023];dp[0][0] = 1;for (int i = 1; i <= 2022; i++) {for (int j = 10; j >= 1; j--) {for (int k = 2022; k >= i; k--) {dp[j][k] += dp[j - 1][k - i];}}}System.out.println(dp[10][2022]);}