解法:
对于该题有以下错误(敬希评论区指正
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是最小的