做简单的网站链接关键洞察力

题目

有一名科学家想要从一台古董电脑中拷贝文件到自己的电脑中加以研究。但此电脑除了有一个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），查看当前专栏更新的所有题目。