c++用dfs写代码有n个任务在k个可并行工作的机器上执行。每个任务需要执行t时间,请你设计一个算法,找出完成这n个任务的最佳调度,使得完成全部任务的时间最短。 输入 测试样例由多组测试数据组成。 每个样例包含两行,第一行输入两个正整数n和k; 第二行输入n个整数ti,表示每个任务需要运行的时间。 1 <= n,k <= 20,1 <= ti <= 100 输出 对每个测试例,输出一行,表示结果。
时间: 2024-02-18 08:04:09 浏览: 24
好的,我可以为您提供一个使用深度优先搜索(DFS)的 C++ 代码示例。
假设我们有n个任务需要在k个可并行工作的机器上执行,每个任务需要执行t时间。我们需要找到完成这n个任务的最佳调度,使得完成全部任务的时间最短。我们可以使用 DFS 来实现此目标。
具体地,我们可以将每个任务按照所需时间从大到小排序。然后,我们从第一个任务开始,依次将其分配给k台机器中当前总时间最小的那台机器。每次分配任务时,我们可以记录当前各机器的总时间,并在后续搜索中使用这些信息来优化搜索过程。为了避免重复搜索,我们需要使用一个布尔数组来记录哪些任务已经被分配到了机器上。当我们完成所有任务的分配后,我们可以计算出完成所有任务所需的时间,并将其与当前最短时间进行比较,从而更新最短时间。
以下是 C++ 代码示例:
```c++
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 25;
int n, k;
vector<int> tasks;
int machines[N];
bool vis[N];
int ans;
void dfs(int u, int t) {
if (t >= ans) {
return;
}
if (u == n) {
ans = t;
return;
}
int used[N], min_time = 1e9;
memset(used, 0, sizeof(used));
for (int i = 0; i < k; i++) {
used[machines[i]] = 1;
min_time = min(min_time, machines[i]);
}
for (int i = 0; i < n; i++) {
if (!vis[i]) {
vis[i] = true;
for (int j = 0; j < k; j++) {
if (machines[j] == min_time) {
machines[j] += tasks[i];
dfs(u + 1, max(t, machines[j] - tasks[i]));
machines[j] -= tasks[i];
}
}
vis[i] = false;
}
}
}
int main() {
while (cin >> n >> k) {
tasks.resize(n);
for (int i = 0; i < n; i++) {
cin >> tasks[i];
}
sort(tasks.begin(), tasks.end(), greater<int>());
memset(vis, false, sizeof(vis));
memset(machines, 0, sizeof(machines));
ans = 1e9;
dfs(0, 0);
cout << ans << endl;
}
return 0;
}
```
在上面的代码中,我们使用了一个全局变量 ans 来记录当前最短时间。当我们找到一种更优的任务调度方案时,我们将其记录下来,并更新 ans 的值。需要注意的是,由于该算法需要遍历所有可能的任务调度方案,因此其时间复杂度较高,为 O(n^k)。