当前位置: 首页 > article >正文

【华为OD题库-026】通过软盘拷贝文件-java

题目

有一名科学家想要从一台古董电脑中拷贝文件到自己的电脑中加以研究。但此电脑除了有一个3.5寸软盘驱动器以外,没有任何手段可以将文件拷贝出来,而且只有一张软盘可以使用。因此这一张软盘是唯一可以用来拷贝文件的载体。科学家想要尽可能多地将计算机中的信息拷贝到软盘中,做到软盘中文件内容总大小最大。已知该软盘容量为1474560字节。文件占用的软盘空间都是按块分配的,每个块大小为512个字节。一个块只能被一个文件使用。拷贝到软盘中的文件必须是完整的,且不能采取任何压缩技术。
输入描述
第1行为一个整数N,表示计算机中的文件数量。1<= N<= 1000
接下来的第2行到第N+1行(共N行),每行为一个整数,表示每个文件的大小Si,单位为字节.0<=i<N;i<=Si
输出描述
科学家最多能拷贝的文件总大小
备注
为了充分利用软盘空间,将每个文件在软盘上占用的块记录到本子上。即真正占用软盘空间的只有文件内容本身
示例1:
输入
3
737270
737272
737288
输出
1474542
说明
3个文件中,每个文件实际占用的大小分别为737280字节737280字节、737792字节。
只能选取前两个文件,总大小为1474542字节。虽然后两个文件总大小更大且未超过1474560字节,但因为实际占用的大小超过了1474560字节,所以不能选后两个文件。
示例2:
输入
6
400000
200000
200000
200000
400000
400000
输出
1400000
说明
从6个文件中,选择3个大小为400000的文件和1个大小为200000的文件,得到最大总大小为1400000;
也可以选择2个大小为400000的文件和3个大小为200000的文件,得到的总大小也是1400000.

思路

题目翻译过来就是:在N个数字中选若干数字(子集),使其占用的总的块大小(大小/512.0)不超过1474560/512=2880。求所有子集中容量的最大值?需要注意的是:

一个块只能被一个文件使用,假设一个文件大小为737270,转为块大小:737270/512.0=1439.98046875,此处不管小数部分是多少,都只能向上取整(超出一点点,也只能存到一个新的块中)。即占用1440个块大小,实际占用空间为1440 * 512=737280。

可以有两种思路来解决:

  1. 按照组合的思想,找出所有满足条件的组合,然后求容量最大值
  2. 典型的背包问题,可用动态规划解决

组合思想之前写过博客专门介绍,本文不赘述,直接给出题解。传送门:【JAVA-排列组合】一个套路速解排列组合题

本节重点介绍动态规划思想。

定义二维数组:
dp[i][j]:代表从数组nums的前(i+1)个文件(即nums[0:i])中选则任意个文件,使其占用的block不超过j,能够得到的文件的最大大小总和。

  1. 确定i的取值范围:i刚好对应nums的下标。范围为[0,nums.length-1]
  2. 确定j的取值范围:根据题目描述,最大block为:1474560/512=2880个,范围为[0,2880]
  3. 因此,dp初始化时,可以写为new int[nums.length][2881]

初始化dp

1.dp[i][0]代表,最多选nums前(i+1)个文件,使其占用的block个数不超过0时的最大文件和,很明显只要选了文件,其占用的block就不可能为0个,所以dp[i][0]=0
2.dp[0][j]代表,最多选取第一个文件,即nums[0],使其占用空间不超过j个block时的最大文件和。首先需要计算选则的文件占用的block大小:curBlock=Math.ceil(nums[0] / 512.0),如果j的大小比curBlock还小,说明不能放入nums[0]这个文件,反之,如果j>=curBlock,那么此时的dp[0][j]=nums[0]。

确定递推关系

对于dp[i][j](i>=1,j>=1)来说。对于当前文件nums[i]只有选取或者不选取两种状态:记录当前nums[i]文件占用的block大小为:curBlock=Math.ceil(nums[i] / 512.0)。
不选取:不选取就是从前i-1个元素中去选取不超过j个block大小的结果,那么dp[i][j]=dp[i-1][j]
选取:此时的结果应该等于未选当前值的结果+当前值的大小。即:dp[i-1][j-curBlock]+nums[i]
最后dp[i][j]取两种状态的最大值即可,即dp[i][j]=max(dp[i-1][j],dp[i-1][j-curBlock]+nums[i])

有了初始值和递推关系,可以得到我们需要的结果:dp[nums.length-1][2880]

题解

方案一:组合思想

package hwod;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;

public class CopyFileFromSoftDisk {
    private static int max_block = (int) Math.ceil(1474560 / 512.0);
    private static int ans = -1;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }
        System.out.println(copyFileFromSoftDisk(nums));
    }

    private static int copyFileFromSoftDisk(int[] nums) {
        LinkedList<Integer> path = new LinkedList<>();
        Arrays.sort(nums);
        int[] used = new int[nums.length];
        dfs(nums, 0, path, used, 0, 0);
        return ans;
    }

    private static void dfs(int[] nums, int begin, LinkedList<Integer> path, int[] used, int sum, int block) {
        if (block > max_block) return;
        ans = Math.max(sum, ans);
        for (int i = begin; i < nums.length; i++) {
            if (i > begin && nums[i] == nums[i - 1] && used[i - 1] == 0) break;//同层重复剪枝
            path.addLast(nums[i]);
            used[i] = 1;
            dfs(nums, i + 1, path, used, sum + nums[i], block + (int) Math.ceil(nums[i] / 512.0));
            path.removeLast();
            used[i] = 0;
        }
    }
}

方案二:动态规划

package hwod;

import java.util.Scanner;

public class CopyFileFromSoftDisk2 {
    private static int max_block = (int) Math.ceil(1474560 / 512.0);
    private static int ans = -1;
    private static int cnt = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }
        System.out.println(copyFileFromSoftDisk(nums));
    }


    private static int copyFileFromSoftDisk(int[] nums) {
        int m = nums.length, n = max_block;
        int[][] dp = new int[m][n + 1];
        for (int i = (int) Math.ceil(nums[0] / 512.0); i < n + 1; i++) {
            dp[0][i] = nums[i];
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n + 1; j++) {
                int curBlock = (int) Math.ceil(nums[i] / 512.0);
                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - curBlock] + nums[i]);
            }
        }
        return dp[m - 1][n];
    }
}

推荐

如果你对本系列的其他题目感兴趣,可以参考华为OD机试真题及题解(JAVA),查看当前专栏更新的所有题目。


http://www.kler.cn/a/137129.html

相关文章:

  • LabVIEW伸缩臂参数监控系统
  • Leaflet的zoom层级-天地图层级之间的关系
  • 常用es命令
  • 【系统】Windows11更新解决办法,一键暂停
  • Android详解——ConstraintLayout约束布局
  • [Python学习日记-73] 面向对象实战1——答题系统
  • DITTEL控制器维修SENSITRON6-2AE
  • chrome 插件 Mobile simulator
  • 没收到Win11 23H2正式版的推送怎么升级到23H2
  • 第1关:图的邻接表存储及求邻接点操作
  • 让别人访问电脑本地
  • java算法学习索引之数组矩阵问题
  • 第2关:图的深度优先遍历
  • 重装系统后如何恢复以前的文件?详细教程大揭秘!
  • 进程和线程( Process and Thread)
  • python -opencv形态学操作
  • Codeforces Round 910 (Div. 2) --- B-E 补题记录
  • 1.0 Zookeeper 教程
  • 用二维码进行人员管理,人员信息一目了然
  • 深度剖析倍增算法求解最近公共祖先(LCA)的细枝末节
  • 使用DHorse发布SpringBoot项目到K8S
  • Flutter打包iOS过程中pod访问github失败
  • # 学习 Prolog 和 离散逻辑的16个等价公式:一趟有趣的逻辑之旅
  • [C++11]可变参数模板和参数包展开
  • 打破传统束缚,释放服务潜能:本地生活服务商聚合系统引领行业新风向!
  • 2013年12月13日 Go生态洞察:Go在App Engine上的工具、测试和并发