侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 674 篇文章
  • 累计创建 128 个标签
  • 累计收到 20 条评论

目 录CONTENT

文章目录

【动态规划】背包与魔法

GabrielxD
2023-02-15 / 0 评论 / 0 点赞 / 98 阅读 / 1,091 字
温馨提示:
本文最后更新于 2023-02-15,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

背包与魔法 - 蓝桥云课


问题描述

小蓝面前有 NN 件物品, 其中第 ii 件重量是 WiW_{i} , 价值是 ViV_{i} 。她还有一个背包, 最大承重是 MM

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

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

输入格式

第一行包含 3 个整数 NMN 、 MKK

以下 NN 行, 每行两个整数 WiW_{i}ViV_{i}

输出格式

一个整数代表答案。

样例输入

3 10 3
5 10
4 9
3 8
copy

样例输出

26
copy

样例说明

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

评测用例规模与约定

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

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

运行限制

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

解题

方法一:动态规划

思路

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

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

普通01背包

思维过程:

img

动态规划:

  • 状态定义:f[i][j]f[i][j] 表示所有只考虑前 ii 个物品,且总体积不大于 jj 的所有选法中能得到的最大价值
  • 状态转移方程:f[i][j]=max(f[i1][j],f[i1][jv[i]]+w[i])f[i][j] = \max(f[i-1][j], f[i-1][j - v[i]] + w[i])v[i]jv[i] \le j)。
  • 初始状态:只考虑前 00 个物品的时候没有物品可选,最大价值一定是 00
使用魔法时的01背包

思维过程:

image-20230215044356879

动态规划:

  • 状态定义:g[i][j]g[i][j] 表示所有只考虑前 ii 个物品,总体积不大于 jj 且使用魔法的所有选法中能得到的最大价值
  • 状态转移方程:g[i][j]=max{g[i1][j]g[i1][jv[i]]+w[i]jv[i]f[i1][jv[i]k]+2w[i]jv[i]+kg[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}
  • 初始状态:只考虑前 00 个物品的时候没有物品可选,最大价值一定是 00
  • 注意:不选 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]));
    }
}
0

评论区