問題描述：
在一臺超級計算機上，編號為1，2，…，n的n個作業(yè)等待批處理。批處理的任務就是將這n個作業(yè)分成若干批，每批包含相鄰的若干作業(yè)。從時刻0開始，分批加工這些作業(yè)。在每批作業(yè)開始前，機器需要啟動時間S，而完成這批作業(yè)所需的時間是單獨完成批中各個作業(yè)需要時間的總和。單獨完成第i個作業(yè)所需的時間是ti,所需的費用是它的完成時刻乘以一個費用系數(shù)fi。同一批作業(yè)將在同一時刻完成。例如，如果在時刻T開始一批作業(yè)x,x+1,…,x+k,則這一批作業(yè)的完成時刻均為T+S+(tx+tx+1+…+tx+k)。最優(yōu)批處理問題就是要確定總費用最小的批處理方案。例如，假定有5個作業(yè)等待批處理，且S=1,(t1,t2,t3,t4,t5)=(1,3,4,2,1),(f1,f2,f3,f4,f5)=(3,2,3,3,4)。如果采用批處理方案{1,2}，{3}，{4,5}，則各作業(yè)的完成時間分別為（5,5,10,14,14），各作業(yè)的費用分別為（15,10,30,42,56），因此，這個批處理方案總費用是153。

算法設計：
對于給定的待批處理的n個作業(yè)，計算其總費用最小的批處理方案。
數(shù)據(jù)輸入：
由文件Input.txt提供輸入數(shù)據(jù)。文件的第1行是待批處理的作業(yè)數(shù)n，第2行是啟動時間S。接下來每行有2個數(shù)，分別為單獨完成第i個作業(yè)所需的時間是ti和所需的費用系數(shù)fi。
結果輸出：
將計算出的最小費用輸出到文件output.txt中。

輸入文件示例
Input.txt output.txt
5 153
1
1 3
3 2
4 3
2 3
1 4

設計思路：
分析題目，因為每批完成的作業(yè)必須相鄰，即只能{1，2}{3}，不能{1，3}{2}，因此可以用動態(tài)規(guī)劃來解決。設置一個minBatchCost數(shù)組，minBatchCost[i][t]表示處理第i到第n-1個作業(yè)，從時間t開始的最小開銷。調用minBatchCost[0][0]，即為處理第0個作業(yè)到第n-1個作業(yè)，從0時刻開始的最小開銷，即為題目所求。
對于待處理作業(yè)i到n-1，不斷求出第i到i+1,i到i+2……i到n-1的最小花費并填入minBatchCost。只要沒有計算到第n-1個作業(yè)，就遞歸處理后面的任務，直到處理完所有的作業(yè)。

#include <bits/stdc++.h> using namespace std;const int N = 10000; const int M = 1e4;int n,s; int t[N+10],f[N+10]; int tt[N+10],ff[N+10]; int dp[N+10];int main(){//freopen("C://Users//Administrator//Desktop//測試數(shù)據(jù)//ch3//prog32//test//batch20.in","r",stdin);cin >> n;cin >> s;for (int i = 1;i <= n;i++) cin >> t[i] >> f[i];for (int i = n;i >= 1;i--){tt[i] = tt[i+1] + t[i];ff[i] = ff[i+1] + f[i];}dp[n+1] = 0;for (int i = n;i >= 1;i--){dp[i] = -1;for (int j = i+1;j <= n+1;j++){int temp = dp[j] + ff[i]*(s+tt[i]-tt[j]);if (dp[i]==-1) dp[i] = temp;else dp[i] = min(dp[i],temp);}}printf("%d\n",dp[1]);return 0; } 超強干貨來襲 云風專訪：近40年碼齡，通宵達旦的技術人生

總結

以上是生活随笔為你收集整理的在一台超级计算机上，编号为1，2，…，n的n个作业等待批处理。批处理的任务就是将这n个作业分成若干批，每批包含相邻的若干作业。从时刻0开始，分批加工这些作业。在每批作业开始前，机器需要启动时间S，而完的全部內容，希望文章能夠幫你解決所遇到的問題。

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