第十三届蓝桥杯JavaB组国赛G题——背包与魔法 (AC)

1.背包与魔法

1.问题描述

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

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

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

2.输入格式

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

以下 $N$ 行, 每行两个整数 $W_i$和$V_i$。

3.输出格式

一个整数代表答案。

4.样例输入

3 10 3
5 10
4 9
3 8

5.样例输出

26

6.数据范围

$1\le N\le 2000,1\le M,K\le 10000,0\le W_i,V_i\le 10000$

7.原题链接

背包与魔法

2.解题思路

  首先，想解决此题的前置知识是需要掌握普通的$01$背包问题，当然这题肯定不可能这么简单。题目相对于$01$背包来说,唯一的区别仅仅在于小蓝可以使用$1$次魔法。我们只需要多加一维状态记录是否使用了魔法即可,下面考虑$dp$状态。

  $f[i][j][0]$：表示只考虑前$i$个物品，背包容量为$j$，并且还没有使用魔法的情况下的最大价值。我们考虑对该状态进行转移,因为这一状态是未使用魔法的，所以转移方程同$01$背包一样。
$$f[i][j][0]=\{\begin{array}{ll}f[i-1][j][0]& \text{当 j<w[i]}\\ max(f[i-1][j][0],f[i-1][j-w[i]][0])& \text{当 j>=w[i]}\end{array}$$

  $f[i][j][1]$：表示只考虑前$i$个物品，背包容量为$j$，并且已经使用了魔法 (注意并不一定是对第$i$个物品使用) 的情况下的最大价值。考虑每个背包的选择情况的，我将其分为三种情况考虑。

1. 对于当前物品$i$，如果满足$w[i]>j$，那么说明该物品无法选择，更不用考虑是否对该物品使用魔法。
2. 如果在不符合情况$1$的情况下,此时满足$w[i]+k>j$,那么我们是无法对该背包使用魔法的，因为使用以后物品重量超过了背包重量，但我们是可以在不使用魔法的情况下选择该物品。
3. 如果此时满足$w[i]+k<=j$，那么说明我们可以使用魔法选择该物品。
4. 对三种情况进行细讲，首先第一种，因为根本选不了背包，所以状态转移只有一种情况。对于第二种情况，虽然我们可以选择此物品，但我们也可以不选择它，两者情况取最大值。对于第三种情况，我们可以不选它，也可以选它，也可以使用魔法选它，存在三种情况，我们三种情况取最大值。这里需要注意的是，当我们对该背包使用魔法时，转移时应该是前面没有使用魔法的状态，即最后一维状态是$0$，因为魔法只能用一次。
   状态转移
   f [ i ] [ j ] [ 1 ] = { f [ i − 1 ] [ j ] [ 1 ] 1 m a x ( f [ i − 1 ] [ j − w [ i ] ] [ 0 ] + v [ i ] , f [ i ] [ j ] [ 0 ] ) 2 m a x ( m a x ( f [ i ] [ j ] [ 1 ] , f [ i − 1 ] [ j − w [ i ] ] [ 1 ] + v [ i ] ) , f [ i − 1 ] [ j − ( w [ i ] + k ) ] [ 0 ] + v [ i ] ∗ 2 ) 3 f[i][j][1]=
   {f[i−1][j][1]1max(f[i−1][j−w[i]][0]+v[i],f[i][j][0])2max(max(f[i][j][1],f[i−1][j−w[i]][1]+v[i]),f[i−1][j−(w[i]+k)][0]+v[i]∗2)3" role="presentation">⎧⎩⎨f[i−1][j][1]max(f[i−1][j−w[i]][0]+v[i],f[i][j][0])max(max(f[i][j][1],f[i−1][j−w[i]][1]+v[i]),f[i−1][j−(w[i]+k)][0]+v[i]∗2)123$$\{\begin{array}{ll}f[i-1][j][1]& \text{1}\\ max(f[i-1][j-w[i]][0]+v[i],f[i][j][0])& \text{2}\\ max(max(f[i][j][1],f[i-1][j-w[i]][1]+v[i]),f[i-1][j-(w[i]+k)][0]+v[i]\ast 2)& \text{3}\end{array}$$
   f[i][j][1]=⎩ ⎨ ⎧​f[i−1][j][1]max(f[i−1][j−w[i]][0]+v[i],f[i][j][0])max(max(f[i][j][1],f[i−1][j−w[i]][1]+v[i]),f[i−1][j−(w[i]+k)][0]+v[i]∗2)​123​

  因为问题本质还是属于$01$背包问题，所以我们可以使用滚动数组进代码进行时间复杂度和空间复杂的优化，压缩一维状态，状态转移可以写成：
$$f[i][1]=\{\begin{array}{ll}max(f[j-w[i]][0]+v[i],f[j][0])& \\ max(max(f[j][1],f[j-w[i]][1]+v[i]),f[j-(w[i]+k)][0]+v[i]\ast 2)& \end{array}$$

3.Ac_code

import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Scanner;

public class Main {
    static PrintWriter out=new PrintWriter(new OutputStreamWriter(System.out));
    static int N=2010,M=10010;
    static int[] w=new int[N];
    static int[] v=new int[N];
    static long[][] f=new long[M][2];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int k = sc.nextInt();
        for (int i = 1; i <= n; i++) {
            w[i] = sc.nextInt();
            v[i] = sc.nextInt();
        }
        for (int i = 1; i <= n; i++) {
            //j是容积
            for (int j = m; j >=w[i]; j--) {
                //如果能选且还没有使用魔法
                f[j][0]=Math.max(f[j-w[i]][0]+v[i],f[j][0]);
                //已经使用过魔法了
                if (w[i]+k<=j){
                    f[j][1]=Math.max(Math.max(f[j][1],f[j-w[i]][1]+v[i]),f[j-(w[i]+k)][0]+v[i]* 2L);
                }
            }
        }
        out.println(Math.max(f[m][1],f[m][0]));
        out.flush();
    }
}