3
737270
737272
737288
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

1474542
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

6
400000
200000
200000
200000
400000
400000
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

1400000
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

import math

# knapsack 函数：计算给定文件集合能够放入背包中的最大文件大小
def knapsack(idx, remaining_capacity, memo):
    # 递归的终止条件：如果所有文件都处理完，或者背包容量为 0
    if idx == len(arr) or remaining_capacity == 0:
        return 0

    # 检查当前子问题是否已经计算过，避免重复计算
    if (idx, remaining_capacity) in memo:
        return memo[(idx, remaining_capacity)]

    # 计算当前文件的大小，文件大小需要向上取整为 512 的倍数
    file_size = math.ceil(arr[idx] / 512.0) * 512
    
    # 如果当前文件大小大于剩余容量，跳过当前文件，递归处理下一个文件
    if file_size > remaining_capacity:
        result = knapsack(idx + 1, remaining_capacity, memo)
    else:
        # 否则，选择放入当前文件或者不放，取两者的最大值
        result = max(
            knapsack(idx + 1, remaining_capacity, memo),  # 不放当前文件
            knapsack(idx + 1, remaining_capacity - file_size, memo) + arr[idx]  # 放入当前文件
        )

    # 将当前子问题的结果存入 memo 字典中，以便下次直接使用
    memo[(idx, remaining_capacity)] = result
    return result

# getResult 函数：初始化 memo 并调用 knapsack 函数计算结果
def getResult():
    memo = {}  # 初始化一个空的 memo 字典
    capacity = 1474560  # 背包的容量（单位：字节）
    return knapsack(0, capacity, memo)  # 从第一个文件开始递归

# 主程序：读取输入数据并调用 getResult 计算结果
n = int(input())  # 输入文件的数量
arr = [int(input()) for _ in range(n)]  # 输入每个文件的大小（单位：字节）
print(getResult())  # 输出计算得到的最大文件总大小

 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39
• 40

java解法

• 解题思路
• 该代码实现了经典的 0/1 背包问题，目的是通过动态规划（DP）来解决如何将给定大小的文件放入背包中，使得背包的总文件大小最大化。具体到本问题中，文件的大小需要向上取整为 512 字节的整数倍，然后计算在给定容量下可以放入的文件的最大字节总大小。

问题背景
背包问题：你有一个容量有限的背包和一系列的物品（文件）。每个文件有大小，你需要选择放哪些文件，以使得背包中的文件总大小最大。
具体情况：每个文件的大小单位是字节，但必须向上取整为 512 字节的倍数，这意味着文件的大小必须按照 512 字节的单位来存放。
解决方案
背包容量的单位：为了简化问题，背包的容量不再以字节为单位，而是将容量转换为 512 字节的块数。因此，背包容量为 1474560 / 512 = 2880 块。
动态规划：利用动态规划数组 dp[] 来存储在给定背包容量下，最大能够放入的文件字节总数。dp[j] 表示在背包容量为 j 块时，能够获得的最大文件字节总数。
状态转移：对于每个文件，我们尝试将其放入背包，更新 dp[] 数组，最终得到最大能放入的文件字节总和

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 读取文件数量
        int n = sc.nextInt();
        
        // 文件大小数组
        int[] arr = new int[n];
        
        // 读取每个文件的大小
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        // 计算最大可放入背包的文件字节总大小
        System.out.println(getMaxFileSize(n, arr));
    }

    // 动态规划求解最大文件字节总和
    public static int getMaxFileSize(int n, int[] arr) {
        // 背包的容量，单位为512字节块
        int maxCapacity = 1474560 / 512;  // 2880块

        // 动态规划数组，dp[i]表示容量为i块时，能装入的最大字节数
        int[] dp = new int[maxCapacity + 1];  // 数组长度为最大容量+1

        // 遍历每个文件
        for (int i = 0; i < n; i++) {
            // 当前文件占用的背包容量，单位为512字节块
            int weight = (int) Math.ceil(arr[i] / 512.0);  // 向上取整，单位为512字节块
            // 当前文件的字节数
            int worth = arr[i];  // 文件的字节大小

            // 更新动态规划数组，从后往前更新，避免重复使用同一个文件
            for (int j = maxCapacity; j >= weight; j--) {
                dp[j] = Math.max(dp[j], dp[j - weight] + worth);
            }
        }

        // 返回背包容量为maxCapacity时能装入的最大字节数
        return dp[maxCapacity];
    }
}

 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">