日志文件存储问题 - 华为机试真题题解

考试平台： 时习知

分值： 300分

考试时间： 两小时（共3题）

题目描述

有一个日志管理系统，保存了N个进程的日志文件，每个进程有M个日志文件。系统记录了每个日志文件的文件大小和被下载的次数。

现在需要把部分日志文件保存在容量为C的U盘中，请设计算法计算U盘存储的日志文件下载次数之和最大是多少。

注意，为了保证日志的完整性，每个进程至少要保存一个日志文件到U盘，如果无法实现，则返回-1，如果U盘容量足以存储，则返回所存储的日志文件被下载的次数之和。

输入

载分为多行输入：

• 第1行输入的输入信息是N、M、C，用空格分割。
• 第2行开始是日志文件的信息，每行信息包含了所属进程序号、文件大小和被下载次数，用空格分割。

输入范围说明：

• 0 < N <= 100
• 0 < M <= 1000
• 0 < C <= 100
• 0 < 每个日志文件大小 <= 20
• 0 < 每个日志文件被下载次数 <= 10000

输出

U盘存储的日志文件被下载次数之和，每个进程至少要保存一个日志文件到U盘，如果无法实现，则返回-1。

示例1

输入：
1 2 10
0 5 1
0 5 2

输出：
3

解释： 
有1个进程，每个进程有2个日志文件，U盘容量是10，第一个进程的第一个文件大小是5，下载次数是1;第一个进程的第二个文件大小是5，下载次数是2。
U盘能存储这两个文件，下我次数之和最多是3次。

示例2

输入：
1 2 1
0 5 1
0 5 2

输出：
-1

解释： 
U盘容量不足，如果无法实现，则返回-1。

题解

这个问题可以看作一个“分组背包问题”，其中每个进程的日志文件就是一组物品。我们需要从每个进程中至少选择一个日志文件，并且在容量限制下，尽可能让被下载的次数之和最大化。

具体来说：

• 每个进程有多个日志文件，每个文件有大小和下载次数。
• 我们需要从每个进程的文件中选至少一个，使得这些选中的文件总大小不超过给定的U盘容量，并且使得被下载的次数最大。
• 如果无法满足条件，即容量不够存放每个进程至少一个文件，则返回 -1。

解题思路

1. 分组背包问题：
   • 对于每个进程，至少选择一个文件。
   • 每个文件可以看作一个物品，大小是文件大小，价值是下载次数。
   • 由于每个进程至少选一个文件，这相当于在背包问题中，物品被分为组，每组至少选一个物品。
2. 动态规划：
   • 用 dp[i][c] 表示前 i 个进程在容量 c 下最多能获得的下载次数。
   • 对于每个进程，考虑从该进程的日志文件中选出一个或多个文件，然后更新dp数组。
   • 每个进程的选择是独立的，但整体上需要在每个进程中至少选择一个文件。
3. 初始化：
   • 我们需要初始化动态规划数组，表示初始状态下不选择任何文件时的结果。
4. 状态转移：
   • 对于每个进程，枚举所有文件，并更新dp数组，类似于背包问题的处理。

C++

#include <bits/stdc++.h>

using namespace std;

// dp[g][c] 表示选择了 g 个进程(每个进程至少选一个日志)容量为 c 时最多下载次数
int dp[105][105];
// w[pix][0...M-1] 存储pid进程M个日志文件的大小, w[pix][1000] 表示pid日志文件当前存在的个数
int w[105][1010];
// w[pix][0...M-1] 存储pid进程M个日志文件下载次数, w[pix][1000] 表示pid日志文件当前存在的个数
int v[105][1010];

int main() {
    // N 个进程, 每个进程M个日志文件， 容量C
    int N, M, C;
    cin >> N >> M >> C;

    for (int i = 0; i < N * M; i++) {
        int pid, fsize, cnt;
        cin >> pid >> fsize >> cnt;

        w[pid][w[pid][1000]++] = fsize;
        v[pid][v[pid][1000]++] = cnt;
    }

    memset(dp, -1, sizeof(dp));
    memset(dp[0], 0, sizeof(dp[0]));

    for (int pid = 0; pid < N; pid++) {     // 组
        for (int i = 0; i < M; i++) {       // 组内物品
            for (int x = C; x > 0; x--) {   // 容量
                if (x - w[pid][i] >= 0) {
                    if (dp[pid][x - w[pid][i]] >= 0) {
                        dp[pid + 1][x] = max(dp[pid + 1][x], dp[pid][x - w[pid][i]] + v[pid][i]);
                    }
                    if (dp[pid + 1][x - w[pid][i]] >= 0) {
                        dp[pid + 1][x] = max(dp[pid + 1][x], dp[pid + 1][x - w[pid][i]] + v[pid][i]);
                    }
                }
            }
        }
    }

    int ans = -1;
    for (int x: dp[N]) ans = max(ans, x);
    cout << ans << endl;

    return 0;
}
/*
1 2 10
0 5 1
0 5 2

1 2 1
0 5 1
0 5 2

2 2 10
0 5 1
0 5 2
1 5 5
1 5 5

2 2 20
0 5 1
0 5 2
1 5 5
1 5 5

2 2 30
0 5 1
0 5 2
1 5 5
1 5 5
 */

🙏整理题解不易， 如果有帮助到您，请给点个赞 ‍❤️‍ 和收藏 ⭐，让更多的人看到。🙏🙏🙏