华为OD机试 通过软盘拷贝文件

题目描述

有一名科学家想要从一台古董电脑中拷贝文件到自己的电脑中加以研究但此电脑除了有一个3.5寸软盘驱动器以外，没有任何手段可以将文件持贝出来，而且只有一张软盘可以使用.因此这一张软盘是唯一可以用来拷贝文件的载体。

科学家想要尽可能多地将计算机中的信息拷贝到软盘中，做到软盘中文件内容总大小最大.已知该软盘容量为1474560字节。文件占用的软盘空间都是按块分配的，每个块大小为512个字节.个块只能被一个文件使用。拷贝到软盘中的文件必须是完整的，且不能采取任何压缩技术

输入描述第1行为一个整数N，表示计算机中的文件数量。1≤ N < 1000.接下来的第2行到第N+1行(共N行)，每行为一个整数，表示每个文件的大小Si，单位为字节.0<i< N，0< Si< 1000000

输出描述

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

备注

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

用例

输入

3

737270

737272

737288

输出

1474542

动态规划 二维dp数组和滚动数组两个解

二维递推式含义：当前点dp值=max(能放入编号i之前所有文件的情况下页的数量为j时能存储的最大实际文件大小,能放入编号i之前所有文件的情况下页的数量为（j-文件i所占空间）时能存储的最大实际文件大小+文件i实际文件大小)

即dp[i - 1][j]=能放入编号i之前所有文件的情况下，页的数量为j时能存储的最大实际文件大小（不选择放入文件i）

dp[i - 1][j - block[i]] + byte[i]=能放入编号i之前所有文件的情况下，页的数量为（j-文件i所占空间）时能存储的最大实际文件大小+文件i实际文件大小（选择放入文件i）

#include <bits/stdc++.h>
using namespace std;


int main() {
    int num;
    vector<int>byte;//存储每个文件的大小
    vector<int>block;//存储每个文件所占页数
    cin >> num;
    vector<vector<int>>dp(num,vector<int>(2881,0));//题目给出了总空间和页大小 共2880个页
    int tmp;
    for (int i = 0; i < num; i++) {
        cin >> tmp;
        byte.push_back(tmp);
        if (tmp % 512 == 0) {
            tmp /= 512;
            block.push_back(tmp);
        }
        else {//进一
            tmp /= 512;
            tmp ++;
            block.push_back(tmp);
        }
    }
    for (int i = block[0]; i <2881; i++) {//第一行初始化 第一行代表在仅能放入文件0的情况下，页的数量为i时能存储的最大实际文件大小，空间大小为block[0]之后的元素均初始化为byte[0]
        dp[0][i] = byte[0];
    }
    for (int i = 1; i < num; i++) {
        for (int j = block[i]; j <2881; j++) 
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - block[i]] + byte[i]);
    }
        cout << dp[num-1][2880];
}

滚动数组

include <bits/stdc++.h>
using namespace std;


int main() {
    int num;
    vector<int>byte;//存储每个文件的大小
    vector<int>block;//存储每个文件所占页数
    cin >> num;
    vector<int>dp(2881, 0);//题目给出了总空间和页大小 共2880个页
    int tmp;
    for (int i = 0; i < num; i++) {
        cin >> tmp;
        byte.push_back(tmp);
        if (tmp % 512 == 0) {
            tmp /= 512;
            block.push_back(tmp);
        }
        else {//进一
            tmp /= 512;
            tmp++;
            block.push_back(tmp);
        }
    }
    for (int i = 0; i < num; i++) {
        for (int j = 2880; j >= block[i]; j--)//反向遍历背包
            dp[j] = max(dp[j], dp[j - block[i]] + byte[i]);
    }
    cout << dp[2880];
}