题面描述

有一名科学家想要从一台古董电脑中拷贝文件到自己的电脑中进行研究。该电脑只有一个3.5寸软盘驱动器，且只有一张软盘可以使用，容量为1474560字节。文件的存储是以512字节为块进行分配的，且每个块只能被一个文件使用。科学家希望将尽可能多的文件拷贝到软盘中，以实现软盘中文件内容总大小的最大化。

思路

这个问题可以转化为一个“0-1背包问题”。每个文件可以看作一个物品，文件的大小是物品的重量，软盘的容量是背包的最大承载重量。我们需要选择文件，使得它们的总大小最大，且不超过软盘的容量。

2. 实现思路

1. 输入处理：

   • 读取文件的数量 N。
   • 初始化两个向量：sizes 用于存储文件的字节大小，actual_sizes 用于存储每个文件占用的块数。

2. 块数计算：

   • 对于每个文件，使用 (sizes[i] + BLOCK_SIZE - 1) / BLOCK_SIZE 计算实际占用的块数，确保向上取整。

3. 动态规划数组：

   • 创建一个长度为 bag + 1 的 DP 数组 dp，初始值为 0，用于存储每个容量下的最大字节数。

4. 动态规划计算：

   • 外层循环遍历所有文件，内层循环从后向前遍历 dp 数组，更新每个容量下的最大字节数。
   • 通过 dp[j] = max(dp[j], dp[j - weight] + worth) 更新 DP 数组，确保不会在同一轮次中重复使用文件。

5. 输出结果：

   • 最后输出 dp[bag]，即为在给定软盘容量下能够拷贝的最大字节数。

cpp

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    const int DISK_CAPACITY = 1474560; // 软盘容量
    const int BLOCK_SIZE = 512; // 每个块的大小
    const int bag=DISK_CAPACITY/BLOCK_SIZE;
    int N;
    cin >> N;

    vector<int> sizes(N);
    vector<int> actual_sizes(N);

    // 读取文件大小并计算实际占用空间
    for (int i = 0; i < N; i++) {
        cin >> sizes[i];
        actual_sizes[i] = (sizes[i] + BLOCK_SIZE - 1) / BLOCK_SIZE; // 向上取整到512的倍数
    }

    // 动态规划数组
    vector<int> dp(bag+ 1, 0);

    // 动态规划
    for (int i = 0; i < N; i++) {
        int weight = actual_sizes[i]; // 文件实际占用的块数
        int worth = sizes[i]; // 文件的字节数

        // 从后向前遍历，进行滚动优化
        for (int j = bag; j >= weight; j--) {
            dp[j] = max(dp[j], dp[j - weight] + worth);
        }
    }

    // 输出结果
    cout << dp[bag] << endl;

    return 0;
}

python

def main():
    DISK_CAPACITY = 1474560  # 软盘容量
    BLOCK_SIZE = 512  # 每个块的大小
    bag = DISK_CAPACITY // BLOCK_SIZE  # 计算可用的块数

    N = int(input())  # 输入文件数量
    sizes = [0] * N  # 初始化文件大小列表
    actual_sizes = [0] * N  # 初始化实际占用块数列表

    # 读取文件大小并计算实际占用空间
    for i in range(N):
        sizes[i] = int(input())
        actual_sizes[i] = (sizes[i] + BLOCK_SIZE - 1) // BLOCK_SIZE  # 向上取整到512的倍数

    # 动态规划数组
    dp = [0] * (bag + 1)

    # 动态规划
    for i in range(N):
        weight = actual_sizes[i]  # 文件实际占用的块数
        worth = sizes[i]  # 文件的字节数

        # 从后向前遍历，进行滚动优化
        for j in range(bag, weight - 1, -1):
            dp[j] = max(dp[j], dp[j - weight] + worth)

    # 输出结果
    print(dp[bag])

if __name__ == "__main__":
    main()

java

import java.util.Scanner;

public class DiskCopy {
    public static void main(String[] args) {
        final int DISK_CAPACITY = 1474560; // 软盘容量
        final int BLOCK_SIZE = 512; // 每个块的大小
        final int bag = DISK_CAPACITY / BLOCK_SIZE; // 可用的块数

        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt(); // 输入文件数量
        int[] sizes = new int[N]; // 文件大小数组
        int[] actualSizes = new int[N]; // 实际占用块数数组

        // 读取文件大小并计算实际占用空间
        for (int i = 0; i < N; i++) {
            sizes[i] = scanner.nextInt();
            actualSizes[i] = (sizes[i] + BLOCK_SIZE - 1) / BLOCK_SIZE; // 向上取整到512的倍数
        }

        // 动态规划数组
        int[] dp = new int[bag + 1];

        // 动态规划
        for (int i = 0; i < N; i++) {
            int weight = actualSizes[i]; // 文件实际占用的块数
            int worth = sizes[i]; // 文件的字节数

            // 从后向前遍历，进行滚动优化
            for (int j = bag; j >= weight; j--) {
                dp[j] = Math.max(dp[j], dp[j - weight] + worth);
            }
        }

        // 输出结果
        System.out.println(dp[bag]);
        scanner.close(); // 关闭扫描器
    }
}

题目内容

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

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

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

科学家想要尽可能多地将计算机中的信息拷贝到软盘中，做到软盘中文件内容总大小最大。

已知该软盘容量为1474560字节。文件占用的软盘空间都是按块分配的，每个块大小为512个字节。一个块只能被一个文件使用。拷贝到软盘中的文件必须是完整的，且不能采取任何压缩技术。

输入描述

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

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

$0 ≤ i < N,0 ≤ S_i$

输出描述

科学家最多能拷贝的文件总大小

备注

为了充分利用软盘空间，将每个文件在软盘上占用的块记录到本子上。即真正占用软盘空间的只有文件内容本身。

样例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