OD 算法题 B卷【通过软盘拷贝文件】

通过软盘拷贝文件

• 将计算机中的信息拷贝到软盘中，做到软盘中文件内容总大小最大；
• 软盘容量为1474560字节，文件占用的软盘空间按块分配，每个块大小为512字节。一个块只能被一个文件使用，拷贝到软盘中的文件必须是完整的，且不能压缩；

输入描述:
第一行输入N，表示文件的数量；N在【1,1000】
后续的N行，每行一个整数，表示每个文件的大小Si，单位字节

*输出描述:
最多能拷贝的文件总大小

示例1
输入：
3
737270
737272
737288
输出：
1474542

示例2
输入：
6
400000
200000
200000
200000
400000
400000
输出：
1400000

python实现

• 01背包问题

import math# 输入数据
n = int(input().strip())
nums = []
for i in range(n):nums.append(int(input().strip()))#
dp = [0 for i in range(3000)]  # 索引为空闲块数
for num in nums:# 软盘总有的块数j = 2880# 空闲总块数 大于等于当前 文件需要的块数file_block = math.ceil(num / 512)  # 当前文件占用的块数while j >= file_block:dp[j] = max(dp[j], dp[j - file_block] + num)j -= 1print(dp[2880])