江苏省建设协会网站徐州市城乡和城乡建设厅网站首页

题意

题目链接

K个工人，一共jobs个任务，问怎样分配任务，最短的最长工人完成任务完成时间。

思路

• DFS+剪枝（最大单个工人jobs时间超过ans时间；有限空闲工人拿任务）
• 模拟退火
• dp

代码

// dfs
class Solution {
public:void solve(vector<int> &sum, int &ans, vector<int> &jobs, int index, int used, const int &k, int Max){if (Max >= ans)return;if (index == jobs.size()){ans = Max;return ;}if (used < k){sum[used] = jobs[index];solve(sum, ans, jobs, index + 1, used + 1, k, max(sum[used], Max));sum[used] = 0;}for (int i = 0; i < used; i++){sum[i] += jobs[index];solve(sum, ans, jobs, index + 1, used, k, max(sum[i], Max));sum[i] -= jobs[index];}}int minimumTimeRequired(vector<int>& jobs, int k) {int ans = INT_MAX;vector<int> sum(k, 0);solve(sum, ans, jobs, 0, 0, k, 0);return ans;}
};