蓝桥杯2022年第十三届决赛真题-背包与魔法

题目描述

小蓝面前有 N 件物品，其中第 i 件重量是 Wi，价值是 Vi。她还有一个背包，最大承重是 M。

小蓝想知道在背包称重范围内，她最多能装总价值多少的物品？

特别值得一提的是，小蓝可以使用一个魔法，将一件物品的重量增加 K，同时价值翻倍。(当然小蓝也可以不使用魔法）

输入格式

第一行包含 3 个整数 N、M 和 K。

以下 N 行，每行两个整数 Wi 和 Vi。

输出格式

一个整数代表答案。

样例输入

3 10 3
5 10
4 9
3 8

样例输出

26

思路：
就是在01背包的基础上，加上了一个可以重量+k,价值翻倍的条件而已。一开始理解错了，这是我一大坏习惯，每次都因为看错题而出错，我看成了她这个魔法可以无限使用了。

错误代码

import java.util.*;

public class Main {
	static int N = 200005;
	static int mod = 1000000007;
	static int[]dp = new int [N];
	static char[][] str = new char[1005][1005];
	static int vis[][] = new int [2005][2005];
	static int cnt=1;
	static int n=0;
	static double sum=0;
	static double res = 9999999;
	static int a[][] = new int[2005][2005];
	static Map<Integer,List<int[]>> map = new HashMap<>();
	static int b[][] = new int[2005][2005];
	static int dirx[] ={-1,0,1,0};
	static int diry[] ={0,1,0,-1};
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n =sc.nextInt();
		int m=sc.nextInt();
		int  k =sc.nextInt();
		int w[] = new int[n+1];
		int v[] = new int[n+1];
		for(int i=1;i<=n;i++){
			w[i] = sc.nextInt();
			v[i] = sc.nextInt();
		}
		for(int i=1;i<=n;i++){
			for(int j=m;j>=w[i];j--){
				if(j>=w[i]+k)
					dp[j] = Math.max(dp[j],Math.max(dp[j-w[i]]+v[i],dp[j-w[i]-k]+2*v[i]));
				else
				dp[j] = Math.max(dp[j],dp[j-w[i]]+v[i]);
			}
		}
		System.out.println(dp[m]);
		sc.close();
	}
}

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
34
35
36
37
38
39
40
41

然后发现样例输出中我的输出都比较大，发现那个价值翻倍的魔法只能使用一次。所以我设置了一个二维数组dp[i][j],dp[i][0]表示前i重量未使用魔法得到的最大价值，dp[i][1]表示前i重量已使用魔法得到的最大价值。

状态转移方程：

若不使用魔法，也就是j=0的时候的情况，跟01背包的模板一样，
dp[j][0] = Math.max(dp[j][0],dp[j-w[i]][0]+v[i])
若使用魔法，（要保证j的大小符合条件）
有两种情况，这次的物品使用魔法或者之前其中的一个物品使用魔法
1.若这次物品使用魔法，即Math.max(dp[j-w[i]-k][0]+2*v[i]
2.若之前其中的一个物品使用魔法，即dp[j-w[i]][1]+v[i]
合起来就是dp[j][1] = Math.max(dp[j][1],Math.max(dp[j-w[i]-k][0]+2*v[i],dp[j-w[i]][1]+v[i]));

AC代码

import java.util.*;

public class Main {
	static int N = 200005;
	static int mod = 1000000007;
	static int[][]dp = new int [N][2];
	static char[][] str = new char[1005][1005];
	static int vis[][] = new int [2005][2005];
	static int cnt=1;
	static int n=0;
	static double sum=0;
	static double res = 9999999;
	static int a[][] = new int[2005][2005];
	static Map<Integer,List<int[]>> map = new HashMap<>();
	static int b[][] = new int[2005][2005];
	static int dirx[] ={-1,0,1,0};
	static int diry[] ={0,1,0,-1};
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n =sc.nextInt();
		int m=sc.nextInt();
		int  k =sc.nextInt();
		int w[] = new int[n+1];
		int v[] = new int[n+1];
		for(int i=1;i<=n;i++){
			w[i] = sc.nextInt();
			v[i] = sc.nextInt();
		}
		for(int i=1;i<=n;i++){
			for(int j=m;j>=w[i];j--){
				if(j>=w[i]+k){
					dp[j][0] = Math.max(dp[j][0],dp[j-w[i]][0]+v[i]);	
					dp[j][1] = Math.max(dp[j][1],Math.max(dp[j-w[i]-k][0]+2*v[i],dp[j-w[i]][1]+v[i]));
				}
				else{
					dp[j][0] = Math.max(dp[j][0],dp[j-w[i]][0]+v[i]);
				}
			}
		}
		int sum=0;
		for(int i=0;i<=m;i++){
			sum = Math.max(sum,Math.max(dp[i][1],dp[i][0]));
			//System.out.println(dp[i]);
		}
		System.out.println(sum);
		sc.close();
	}
}
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48