小码哥有严重的拖延症,因此他经常赶deadline(即忙于要完成的任务)。有一天小码哥向你求助,因为要 做的事太多了,只能舍弃一些相对不重要的。小码哥共有 n 项任务,每个任务有重要度I;和需要消耗的时 间t;。小码哥现在还有时间 T,他希望你帮忙写一个程序判断应该选择完成哪些任务使得完成的任务重要 度之和最大。 格式 输入格式:第一行两个整数n(0<n<10000),T(T<2000); 第2至n+1行输入第i项任务的重要度I,和完成需要的时间t(0<I,t<1000)。 输出格式:第一行一个整数,完成任务的重要度之和的最大值; 第二行若干个由空格隔开的整数,从小到大输出最优选择的任务的序号(从1开始)。 样例 1 输入: 4 1000 50 500 75 400 60 300 22 200 输出: 157 2 3 4 备注 当做不完所有任务,但有多个重要度与消耗时间都一样的任务,可以选取其中一部分时,选取编号较小的,例如输入为: 4 1000 50 500 50 500 80 300 22 200 对应输出: 152 1 3 4 上述问题用c++里面的动态规划实现
时间: 2024-04-09 13:28:56 浏览: 17
下面是使用C++实现动态规划解决该问题的代码:
```cpp
#include <iostream>
#include <vector>
using namespace std;
struct Task {
int importance;
int time;
};
vector<int> findOptimalTasks(int n, int T, vector<Task>& tasks) {
vector<vector<int>> dp(n+1, vector<int>(T+1, 0));
vector<vector<bool>> selected(n+1, vector<bool>(T+1, false));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= T; j++) {
if (tasks[i-1].time > j) {
dp[i][j] = dp[i-1][j];
} else {
int option1 = dp[i-1][j];
int option2 = dp[i-1][j - tasks[i-1].time] + tasks[i-1].importance;
if (option2 > option1) {
dp[i][j] = option2;
selected[i][j] = true;
} else {
dp[i][j] = option1;
}
}
}
}
vector<int> selectedTasks;
int i = n, j = T;
while (i > 0 && j > 0) {
if (selected[i][j]) {
selectedTasks.push_back(i);
j -= tasks[i-1].time;
}
i--;
}
return selectedTasks;
}
int main() {
int n, T;
cin >> n >> T;
vector<Task> tasks(n);
for (int i = 0; i < n; i++) {
cin >> tasks[i].importance >> tasks[i].time;
}
vector<int> selectedTasks = findOptimalTasks(n, T, tasks);
int totalImportance = 0;
for (int i = 0; i < selectedTasks.size(); i++) {
totalImportance += tasks[selectedTasks[i]-1].importance;
}
cout << totalImportance << endl;
for (int i = selectedTasks.size()-1; i >= 0; i--) {
cout << selectedTasks[i] << " ";
}
cout << endl;
return 0;
}
```
希望这个C++代码对你有帮助!如果你还有其他问题,请随时提问。
相关推荐
![crx](https://img-home.csdnimg.cn/images/20210720083646.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pptx](https://img-home.csdnimg.cn/images/20210720083543.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)