企业网站做广告,郑州郑东新区,做网站续费要多少钱,遵义网约车租车公司题目 有一名科学家想要从一台古董电脑中拷贝文件到自己的电脑中加以研究。但此电脑除了有一个3.5寸软盘驱动器以外#xff0c;没有任何手段可以将文件拷贝出来#xff0c;而且只有一张软盘可以使用。因此这一张软盘是唯一可以用来拷贝文件的载体。科学家想要尽可能多地将计算…题目 有一名科学家想要从一台古董电脑中拷贝文件到自己的电脑中加以研究。但此电脑除了有一个3.5寸软盘驱动器以外没有任何手段可以将文件拷贝出来而且只有一张软盘可以使用。因此这一张软盘是唯一可以用来拷贝文件的载体。科学家想要尽可能多地将计算机中的信息拷贝到软盘中做到软盘中文件内容总大小最大。已知该软盘容量为1474560字节。文件占用的软盘空间都是按块分配的每个块大小为512个字节。一个块只能被一个文件使用。拷贝到软盘中的文件必须是完整的且不能采取任何压缩技术。 输入描述 第1行为一个整数N表示计算机中的文件数量。1 N 1000 接下来的第2行到第N1行(共N行)每行为一个整数表示每个文件的大小Si单位为字节.0iN;iSi 输出描述 科学家最多能拷贝的文件总大小 备注 为了充分利用软盘空间将每个文件在软盘上占用的块记录到本子上。即真正占用软盘空间的只有文件内容本身 示例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/5122880。求所有子集中容量的最大值需要注意的是 一个块只能被一个文件使用假设一个文件大小为737270转为块大小737270/512.01439.98046875此处不管小数部分是多少都只能向上取整超出一点点也只能存到一个新的块中。即占用1440个块大小实际占用空间为1440 * 512737280。 可以有两种思路来解决 按照组合的思想找出所有满足条件的组合然后求容量最大值典型的背包问题可用动态规划解决 组合思想之前写过博客专门介绍本文不赘述直接给出题解。传送门【JAVA-排列组合】一个套路速解排列组合题 本节重点介绍动态规划思想。 定义二维数组 dp[i][j]代表从数组nums的前i1个文件即nums[0:i]中选则任意个文件使其占用的block不超过j能够得到的文件的最大大小总和。 确定i的取值范围i刚好对应nums的下标。范围为[0,nums.length-1]确定j的取值范围根据题目描述最大block为1474560/5122880个范围为[0,2880]因此dp初始化时可以写为new int[nums.length][2881] 初始化dp 1.dp[i][0]代表最多选nums前(i1)个文件使其占用的block个数不超过0时的最大文件和很明显只要选了文件其占用的block就不可能为0个所以dp[i][0]0 2.dp[0][j]代表最多选取第一个文件即nums[0]使其占用空间不超过j个block时的最大文件和。首先需要计算选则的文件占用的block大小curBlockMath.ceil(nums[0] / 512.0)如果j的大小比curBlock还小说明不能放入nums[0]这个文件反之如果jcurBlock那么此时的dp[0][j]nums[0]。 确定递推关系 对于dp[i][j]i1,j1来说。对于当前文件nums[i]只有选取或者不选取两种状态记录当前nums[i]文件占用的block大小为curBlockMath.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) {LinkedListInteger 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, LinkedListInteger 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查看当前专栏更新的所有题目。
