本文主要是介绍华为OD机试E卷-通过软盘拷贝文件[200分],希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目描述
有一名科学家想要从一台古董电脑中拷贝文件到自己的电脑中加以研究但此电脑除了有一个3.5寸软盘驱动器以外,没有任何手段可以将文件持贝出来,而且只有一张软盘可以使用,因此这一张软盘是唯一可以用来拷贝文件的载体。
科学家想要尽可能多地将计算机中的信息拷贝到软盘中,做到软盘中文件内容总大小最大。已知该软盘容量为1474560字节。文件占用的软盘空间都是按块分配的,每个块大小为512个字节。一个块只能被一个文件使用。拷贝到软盘中的文件必须是完整的,且不能采取任何压缩技术。(1474560/512=2880)
题目输入
第1行为一个整数N,表示计算机中的文件数量。1≤ N < 1000。
第2行到第N+1行(共N行),每行为一个整数,表示每个文件的大小 s,单位为字节.0 < i < N,0< s[i]< 1000000
题目输出
科学家最多能拷贝的文件总大小。
用例1
输入
3
124
623
1652
输出
2399
用例2
输入
3
737270
737272
737288
输出
1474542
用例3
输入
6
400000
200000
200000
200000
400000
400000
输出
1400000
解题思路
-
#define
语句设置了背包的最大容量(
MAX_CAPACITY)和最大物品数量(
MAX_ITEMS`)。 -
dp
数组是一个二维数组,用于存储填充前i
个物品且容量为j
时的最大价值。 -
getResult
函数是解决问题的主要函数,它接受物品价值数组(nums
)和物品数量(n
)作为输入。
4.该函数首先使用memset
将dp
数组初始化为全0。
5.然后它遍历物品(从1到n
)和容量(从1到MAX_CAPACITY
)。
6.对于每个物品i
和容量j
,函数计算存储该物品所需的512单元块(kuai
)数量。如果物品大小不是512的倍数,需要额外增加一个块。
7.如果当前容量j
小于存储当前物品所需的块数,则最大价值就是前一行的值(dp[i-1][j]
)。
8.否则,最大价值是以下两个值的最大值:-前一行的值(dp[i-1][j]
)-前一行容量减去当前物品所需块数后的值加上当前物品价值(dp[i-1][j-kuai] + nums[i-1]
)
9.函数然后打印整个dp
数组,用于调试目的。
10.最后,函数返回填充背包时可获得的最大价值,存储在dp[n][MAX_CAPACITY]
中。
这个解决方案的关键在于使用动态规划来高效地计算填充背包时可获得的最大价值。dp
数组存储了中间结果,用于计算最终解。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#
这篇关于华为OD机试E卷-通过软盘拷贝文件[200分]的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!