594: Maximum Tape Utilization Ratio

解法：

对于该题有以下错误（敬希评论区指正

1.dp定义在全局会wa

struct node {
    int count;  // 当前容量下能够存储的程序数量
    int sum;    // 当前容量下所占用的磁带长度
    vector<int> path;  // 当前容量下选择的程序的路径（存放的程序长度）
}dp[N];

2.不取等于情况会wa

dp[j].sum < dp[j - a[i]].sum + a[i])

3.正序遍历程序会wa

for (int i = 0; i < n; i++)

代码：

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

const int N = 1e4;  // 定义一个常量 N，最大可能的磁带容量大小

int a[N];  // 存储每个程序占用的磁带长度

// 定义一个结构体 node，存储每个容量下的状态
struct node {
    int count;  // 当前容量下能够存储的程序数量
    int sum;    // 当前容量下所占用的磁带长度
    vector<int> path;  // 当前容量下选择的程序的路径（存放的程序长度）
};

int main() {
    int n, m;
    cin >> n >> m;  // 输入程序的数量 n 和磁带的容量 m
    node dp[N];  // dp 数组，用于存储每个磁带容量下的状态

    // 输入每个程序占用的磁带长度
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    // 遍历程序，采用逆序遍历程序
    for (int i = n - 1; i >= 0; i--) {  // 逆序遍历程序，确保每个程序只被选择一次
        // 遍历每个可能的磁带容量，从大到小
        for (int j = m; j >= a[i]; j--) {  // 逆序遍历容量，确保不会重复使用程序
            // 如果选择程序 i 后，存储的程序数更多，或者程序数相同但占用磁带长度更小
            if (dp[j].count < dp[j - a[i]].count + 1 || 
                (dp[j].count == dp[j - a[i]].count + 1 && dp[j].sum <= dp[j - a[i]].sum + a[i])) {
                // 更新 dp[j]：增加程序数量、更新占用的磁带长度和路径
                dp[j].count = dp[j - a[i]].count + 1;  // 更新当前容量 j 下的程序数
                dp[j].sum = dp[j - a[i]].sum + a[i];  // 更新当前容量 j 下的磁带长度
                dp[j].path = dp[j - a[i]].path;  // 继承先前的路径
                dp[j].path.push_back(a[i]);  // 将当前程序加入路径
            }
        }
    }

    // 输出结果：最大存储程序数和最大利用率的磁带长度
    cout << dp[m].count << " " << dp[m].sum << endl;

    // 输出存放在磁带上的每个程序的长度
    for (int i = dp[m].path.size() - 1; i >= 0; i--) {
        cout << dp[m].path[i] << " ";  // 按照逆序输出选中的程序长度
    }
}

解法二：

case1：程序总消耗内存<=磁带长度，输出总程序数，程序总消耗内存

case2：程序总消耗内存>磁带长度，

        1.保证存储最多程序：从小到大依次加入sum直至sum+L[i]>磁带长度

        2.在两侧数组中各选一个交换，交换后得到的磁带长度-sum是最小的