一：題目:寶寶 你要永遠開心，下雪了，多穿點，

輸入格式:
第一行輸入作業個數n。

第二行輸入各任務在機器一上的完成時間。

第三行輸入各任務在機器二上的完成時間。

輸出格式:
最短完成時間和

輸入樣例:

3 2 3 2 1 1 3

結尾無空行
輸出樣例:

18

二：思路

分析題意：
題目是批量處理作業調度，那么我們可以得知，這是讓我們完成一個作業之后再去完成另一個作業

思路:
1.姑且先給我們的作業邊上序號 a,b,c三個作業，那么我們可以得知關于這三個作業的
的安排有6種方式，那么我們的問題就簡單了，這是一個全排列問題
2.回歸本題，我們知道了是全排列問題，我們可以通過回溯法窮舉所有的可行解，然后在
根據可行解求出最優值
3.回溯版的全排列，其實這和分治法那個一樣，都是遞歸求全排列，
<1>:遞歸函數的參數
backtecking(int n,vector &v)
int n:表示我們選擇的是n個作業 從1，2，3…這樣的序列我們來求取
vector &v:這里表示我們遞歸的時候記錄哪些元素我們已經訪問過
<2>:返回的結果
vector<vector > ans; 存放每次的可行結
vector path; 記錄每次的可行解
<3>:橫向for循環 和 縱向的遞歸深度

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

我們單層的for循環是遍歷我們所有的（1，2，3…）
縱向的遞歸：我們選擇的是不斷縮小的我們遍歷的范圍

<4>:遞歸終止條件
path.size() == n時，這時我們的一種可行結果（就是我們的一種安排作業的順序 比如1，2，3或則2，1，3）

4:對上方的所有可行解求出最優解

5：圖解

三:上碼

/**分析題意：題目是批量處理作業調度，那么我們可以得知，這是讓我們完成一個作業之后再去完成另一個作業思路:1.姑且先給我們的作業邊上序號 a,b,c三個作業，那么我們可以得知關于這三個作業的的安排有6種方式，那么我們的問題就簡單了，這是一個全排列問題2.回歸本題，我們知道了是全排列問題，我們可以通過回溯法窮舉所有的可行解，然后在根據可行解求出最優值3.回溯版的全排列，其實這和分治法那個一樣，都是遞歸求全排列，<1>:遞歸函數的參數backtecking(int n,vector<bool> &v)int n:表示我們選擇的是n個作業 從1，2，3....這樣的序列我們來求取 vector<bool> &v:這里表示我們遞歸的時候記錄哪些元素我們已經訪問過 <2>:返回的結果vector<vector<int> > ans; 存放每次的可行結 vector<int> path; 記錄每次的可行解<3>:橫向for循環 和 縱向的遞歸深度 for(int i = level; i <= n; i++)我們單層的for循環是遍歷我們所有的（1，2，3...）縱向的遞歸：我們選擇的是不斷縮小的我們遍歷的范圍<4>:遞歸終止條件path.size() == n時，這時我們的一種可行結果（就是我們的一種安排作業的順序 比如1，2，3或則2，1，3） 4:對上方的所有可行解求出最優解 */ #include<bits/stdc++.h> using namespace std;vector<vector<int> > ans; vector<int> path;void backtacking(int n,vector<bool> &v) {//遞歸終止的條件 if(path.size() == n){ans.push_back(path);return;}for(int i = 1; i <= n; i++) {if(v[i] == true) continue;v[i] = true;path.push_back(i);backtacking(n,v);//這里的level+1代表的是我們每次的遍歷范圍在變小 path.pop_back();//當我們得到一種可行解的時候，因為我們要回溯求取其他的解，所以清理最后裝進容器的元素 v[i] = false;} }int main(){int N;vector<int>v1(100),v2(100); vector<bool> v3(100,false);vector<int>v4;//記錄最后每種排列的所求時間和 cin >> N;for (int i = 1; i <= N; i++) { cin >> v1[i];}for (int i = 1; i <= N; i++) {cin >> v2[i];} //cout << v1[1] << ' ' << v1[2] << ' ' << v1[3];backtacking(N,v3);//cout << endl;for (int i = 0; i < ans.size(); i++) {int sumTime1 = 0;int sumTime2 = 0; int sumTime3 = 0;//記錄一種排列最后的完成總時間 for (int j = 0; j < N; j++){//cout << ans[i][j] << ' '; // 1 2 3 int index = ans[i][j];sumTime1 += v1[index];//這里計算在機器1上的完成時間 sumTime2 = sumTime1; //因為在機器二上的完成時間需要在機器1上完成后才可記錄 sumTime2 += v2[index];//這里記錄在機器2上的完成時間 sumTime3 += sumTime2;//記錄所有作業的完成時間和 } v4.push_back(sumTime3);} sort(v4.begin(),v4.end());cout << v4[0];}

寶！我還得再嘮叨一句 記得加油！！永遠愛自己！！

總結

以上是生活随笔為你收集整理的7-2 批处理作业调度 (10 分)（思路+详解）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。