通过软盘拷贝文件

更多关于刷题的内容欢迎订阅我的专栏华为刷题笔记

该专栏题目包含两部分：
100 分值部分题目
200 分值部分题目
所有题目都会陆续更新，订阅防丢失

题目描述

有一名 科学家只 想要从一台古董电脑中拷贝文件到自己的电脑中加以研究。

但此电脑除了有一个3.5寸软盘驱动器以外，没有任何手段可以将文件持贝出来，而且只有一张软盘可以使用。

因此这一张软盘是唯一可以用来拷贝文件的载体。

科学家想要尽可能多地将计算机只中的信息拷贝到软盘中，做到软盘中文件内容总大小最大。已知该软盘容量为 1474560字节。文件占用的软盘空间都是按块分配的，每个块大小为512个字节。一个块只能被一个文件使用。 拷贝到只软盘中的文件必须是完整的，且不能采取任何压缩技术。

输入描述

第1行为一个整数 $N$，表示计算机中的文件数量。$1\le N\le 1000$

接下来的第2行到第 $N+1$ 行(共$N$行)，每行为一个整数，表示每个文件的大小$Si$，单位为字节。

$0\le i<N,0\le 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

题解

0-1 背包问题
背包容量为 1474560 / 512
$d[i][j]=\{\begin{array}{ll}d[i-1][j]& j<w[i]\\ Math.max(dp[i][j],d[i-1][j-w[i]]+value[i])& j>w[i]\end{array}$

源码 Java

public class SoftDisk {static Input input;static {input = new Input("3\n" +"737270\n" +"737272\n" +"737288");input = new Input("6\n" +"400000\n" +"200000\n" +"200000\n" +"200000\n" +"400000\n" +"400000");}static int N = 1474560 / 512;public static void main(String[] args) {int m = Integer.parseInt(input.nextLine()) ;int[] w = new int[m+1];for (int i = 1; i <= m; i++) {w[i] = Integer.parseInt(input.nextLine());}int[][] dp = new int[m+1][N+1];for (int i = 1; i <= m; i++) {int weight = (w[i] + 511) / 512;for (int j = 1; j <= N; j++) {if (j < weight) {dp[i][j] = dp[i-1][j];} else {dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-weight] + w[i]);}}}System.out.println(dp[m][N]);}}