侧边栏壁纸
博主头像
GabrielxD

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

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

目 录CONTENT

文章目录

【动态规划】潜水员

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

题目

1020. 潜水员 - AcWing题库


潜水员为了潜水要使用特殊的装备。

他有一个带2种气体的气缸:一个为氧气,一个为氮气。

让潜水员下潜的深度需要各种数量的氧和氮。

潜水员有一定数量的气缸。

每个气缸都有重量和气体容量。

潜水员为了完成他的工作需要特定数量的氧和氮。

他完成工作所需气缸的总重的最低限度的是多少?

例如:潜水员有5个气缸。每行三个数字为:氧,氮的(升)量和气缸的重量:

3 36 120

10 25 129

5 50 250

1 45 130

4 20 119

如果潜水员需要5升的氧和60升的氮则总重最小为249(1,2或者4,5号气缸)。

你的任务就是计算潜水员为了完成他的工作需要的气缸的重量的最低值。

输入格式

第一行有2个整数 mnm,n 。它们表示氧,氮各自需要的量。

第二行为整数 kk 表示气缸的个数。

此后的 kk 行,每行包括 aibicia_i,b_i,c_i ,3个整数。这些各自是:第 ii 个气缸里的氧和氮的容量及气缸重量。

输出格式

仅一行包含一个整数,为潜水员完成工作所需的气缸的重量总和的最低值。

数据范围

1m211 \le m \le 21 ,
1n791 \le n \le 79 ,
1k10001 \le k \le 1000 ,
1ai211 \le a_i \le 21 ,
1bi791 \le b_i \le 79 ,
1ci8001 \le c_i \le 800

输入样例:

5 60
5
3 36 120
10 25 129
5 50 250
1 45 130
4 20 119

输出样例:

249

解题

方法一:动态规划

思路

【动态规划】二维费用的背包问题的变形。

本题与其说是二维“费用”的背包问题,从题意上来说更接近于二维“价值”的背包问题,因为:显然,氧气和氮气对于潜水来说是价值,而气缸重量是费用。但在实际做题中会发现氧气和氮气在 dp 数组中是下标(也就是“费用”的位置),重量是 dp 数组中存的值(也就是“价值”的位置)。故为了方便从一般背包问题中推广过来,还是把这类问题称为“多维费用(每维费用有至少需求值)求最小价值的背包问题”

思维过程

image-20230217044421645

动态规划
  • 状态定义:f[i][j][k]f[i][j][k] 表示所有只考虑ii 个物品,氧气量至少为 jj 且氮气量至少为 kk 的所有选法中所需要的的最低重量

  • 状态转移方程:f[i][j][k]=min(f[i1][j][k],f[i1][max(0,jm)][max(0,kn)]+w[i])f[i][j][k] = \min(f[i-1][j][k], f[i-1][\max(0, j-m)][\max(0, k-n)] + w[i])

  • 初始状态:只考虑前 00 个物品的时候没有物品可选,最低重量一定是 00 ;在状态转移前不存在任何方案,所以其他状态重量均为无限大

代码

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

public class Main {
    static final int INF = 0x3f3f3f3f;
    
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int M = (int) in.nval;
        in.nextToken();
        int N = (int) in.nval;
        in.nextToken();
        int K = (int) in.nval;
        int[] m = new int[K + 1], n = new int[K + 1], w = new int[K + 1];
        for (int i = 1; i <= K; ++i) {
            in.nextToken();
            m[i] = (int) in.nval;
            in.nextToken();
            n[i] = (int) in.nval;
            in.nextToken();
            w[i] = (int) in.nval;
        }
        int[][][] f = new int[K + 1][M + 1][N + 1];
        for (int[][] a : f) {
            for (int[] b : a) Arrays.fill(b, INF);
        }
        f[0][0][0] = 0;
        for (int i = 1; i <= K; ++i) {
            for (int j = 0; j <= M; ++j) {
                for (int k = 0; k <= N; ++k) {
                    f[i][j][k] = Math.min(f[i - 1][j][k],
                                          f[i - 1][Math.max(0, j - m[i])][Math.max(0, k - n[i])] + w[i]);
                }
            }
        }
        System.out.println(f[K][M][N]);
    }
}

优化:

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

public class Main {
    static final int INF = 0x3f3f3f3f;
    
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int M = (int) in.nval;
        in.nextToken();
        int N = (int) in.nval;
        in.nextToken();
        int K = (int) in.nval;
        int[][] f = new int[M + 1][N + 1];
        for (int[] arr : f) Arrays.fill(arr, INF);
        f[0][0] = 0;
        for (int i = 0; i < K; ++i) {
            in.nextToken();
            int m = (int) in.nval;
            in.nextToken();
            int n = (int) in.nval;
            in.nextToken();
            int w = (int) in.nval;
            for (int j = M; j >= 0; --j) {
                for (int k = N; k >= 0; --k) {
                    f[j][k] = Math.min(f[j][k], f[Math.max(0, j - m)][Math.max(0, k - n)] + w);
                }
            }
        }
        System.out.println(f[M][N]);
    }
}
0

评论区