【动态规划】背包与魔法

题目

背包与魔法 - 蓝桥云课

---

问题描述

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

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

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

输入格式

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

以下 $N$ 行, 每行两个整数 $W_{i}$ 和 $V_{i}$ 。

输出格式

一个整数代表答案。

样例输入

3 10 3
5 10
4 9
3 8
copy

样例输出

26
copy

样例说明

选择第二件和第三件物品, 同时对第二件物品使用魔法。

评测用例规模与约定

对于 $30 \%$ 的数据, $1 \leq N, M, K \leq 100$ .

对于 $100 \%$ 的数据, $1 \leq N \leq 2000,1 \leq M, K \leq 10000,0 \leq W_{i}, V_{i} \leq 10000$ .

运行限制

• 最大运行时间：1s
• 最大运行内存: 512M

解题

方法一：动态规划

思路

本题是01背包的变形，在01背包的基础上增加了“魔法”的概念，且魔法总共只能用一次。

不难想到，可以多开一个动归数组（g）用来维护使用魔法后的状态。

普通01背包

思维过程：

动态规划：

• 状态定义：$f[i][j]$ 表示所有只考虑前 $i$ 个物品，且总体积不大于 $j$ 的所有选法中能得到的最大价值。
• 状态转移方程：$f[i][j] = \max(f[i-1][j], f[i-1][j - v[i]] + w[i])$（$v[i] \le j$）。
• 初始状态：只考虑前 $0$ 个物品的时候没有物品可选，最大价值一定是 $0$。

使用魔法时的01背包

思维过程：

动态规划：

• 状态定义：$g[i][j]$ 表示所有只考虑前 $i$ 个物品，总体积不大于 $j$ 且使用魔法的所有选法中能得到的最大价值。
• 状态转移方程：$g[i][j] = \max\begin{cases} g[i-1][j] \\ g[i-1][j - v[i]] + w[i] & j \ge v[i] \\ f[i-1][j-v[i]-k] + 2*w[i] & j \ge v[i] + k \\ \end{cases}$ 。
• 初始状态：只考虑前 $0$ 个物品的时候没有物品可选，最大价值一定是 $0$。
• 注意：不选 i 和选 i 但不用魔法都属于不在当前状态使用魔法的情况，所以是从 g 之前的状态转移过来的，而选 i 并使用魔法的情况下就必须保证之前一定没有用过魔法，所以要从 j 之前的状态转移。

代码

import java.util.*;
import java.io.*;

public class B_背包与魔法 {
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        in.nextToken();
        int c = (int) in.nval;
        in.nextToken();
        int k = (int) in.nval;
        int[] f = new int[c + 1], g = new int[c + 1];
        for (int i = 0; i < n; ++i) {
            in.nextToken();
            int v = (int) in.nval;
            in.nextToken();
            int w = (int) in.nval;
            for (int j = c; j >= v; --j) {
                f[j] = Math.max(f[j], f[j - v] + w);
                g[j] = Math.max(g[j], g[j - v] + w);
                if (j >= v + k) g[j] = Math.max(g[j], f[j - v - k] + 2 * w);
            }
        }
        System.out.println(Math.max(g[c], f[c]));
    }
}