數(shù)據(jù)結(jié)構(gòu) 雙機(jī)調(diào)度問題的實(shí)例詳解
數(shù)據(jù)結(jié)構(gòu) 雙機(jī)調(diào)度問題的實(shí)例詳解
1.問題描述
雙機(jī)調(diào)度問題,又稱獨(dú)立任務(wù)最優(yōu)調(diào)度：用兩臺(tái)處理機(jī)A和B處理n個(gè)作業(yè)。設(shè)第i個(gè)作業(yè)交給機(jī)器A處理時(shí)所需要的時(shí)間是a[i]，若由機(jī)器B來處理，則所需要的時(shí)間是b[i]?，F(xiàn)在要求每個(gè)作業(yè)只能由一臺(tái)機(jī)器處理，每臺(tái)機(jī)器都不能同時(shí)處理兩個(gè)作業(yè)。設(shè)計(jì)一個(gè)動(dòng)態(tài)規(guī)劃算法，使得這兩臺(tái)機(jī)器處理完這n個(gè)作業(yè)的時(shí)間最短（從任何一臺(tái)機(jī)器開工到最后一臺(tái)機(jī)器停工的總的時(shí)間）。
研究一個(gè)實(shí)例：n=6, a = {2, 5, 7, 10, 5, 2}, b = {3, 8, 4, 11, 3, 4}.
2.代碼
#include <iostream>
#include <stdlib.h>
using namespace std;
int max(int a,int b){
return a>b?a:b;
}
int min(int a,int b){
return a<b?a:b;
}
int main(){
int a[6]={2,5,7,10,5,2};
int b[6]={3,8,4,11,3,4};
int sum_a=0,sum_b=0,T=0,n=6;
for (int i = 1; i <=n; i++)
{
T=max(T,min(sum_a+a[i-1],sum_b+b[i-1]));
if(sum_a+a[i-1]>sum_b+b[i-1]){
sum_b+=b[i-1];
cout<<"任務(wù)"<<i<<"分配給B做"<<endl;
}else{
sum_a+=a[i-1];
cout<<"任務(wù)"<<i<<"分配給A做"<<endl;
}
}
cout<<"總時(shí)間是："<<T<<endl;
}
3.結(jié)果
yaopans-MacBook-Pro:algorithm yaopan$ g++ exercise5-2.cpp yaopans-MacBook-Pro:algorithm yaopan$ ./a.out 任務(wù)1分配給A做 任務(wù)2分配給A做 任務(wù)3分配給B做 任務(wù)4分配給B做 任務(wù)5分配給A做 任務(wù)6分配給A做 總時(shí)間是：15
以上就是數(shù)據(jù)結(jié)構(gòu)雙機(jī)調(diào)度的實(shí)例，如有疑問請(qǐng)留言或者到本站社區(qū)交流討論，感謝閱讀，希望能幫助到大家，謝謝大家對(duì)本站的支持！
相關(guān)文章
C++中對(duì)象的常引用、動(dòng)態(tài)建立和釋放相關(guān)知識(shí)講解
這篇文章主要介紹了C++中對(duì)象的常引用、動(dòng)態(tài)建立和釋放相關(guān)知識(shí)講解,是C++入門學(xué)習(xí)中的基礎(chǔ)知識(shí),需要的朋友可以參考下2015-09-09
一般我們編程的時(shí)候，函數(shù)中形式參數(shù)的數(shù)目通常是確定的，在調(diào)用時(shí)要依次給出與形式參數(shù)對(duì)應(yīng)的實(shí)際參數(shù)。但在某些情況下我們希望函數(shù)的參數(shù)個(gè)數(shù)可以根據(jù)需要確定，因此c語(yǔ)言引入可變參數(shù)函數(shù)。典型的可變參數(shù)函數(shù)的例子有printf()、scanf()等,下面我就開始講解2013-11-11
C語(yǔ)言創(chuàng)建動(dòng)態(tài)dll和調(diào)用dll(visual studio 2013環(huán)境下)
本篇文章主要介紹了C語(yǔ)言創(chuàng)建動(dòng)態(tài)dll和調(diào)用dll(visual studio 2013環(huán)境下)，非常具有實(shí)用價(jià)值，需要的朋友可以參考下2017-11-11
字符串是C語(yǔ)言中最重要的數(shù)據(jù)類型之一,最近借助《C Primer Plus》一書來學(xué)習(xí)C中的常用字符串操作,在此作為筆記記錄,下面這篇文章主要給大家介紹了C語(yǔ)言學(xué)習(xí)筆記之字符串間的那些事,需要的朋友可以參考下2022-04-04
這篇文章主要介紹了C++ COM編程的學(xué)習(xí)過程，在C++中,可以使用抽象基類來實(shí)現(xiàn)COM接口,需要的朋友可以參考下，希望能夠給你帶來幫助2021-09-09
???????C語(yǔ)言實(shí)現(xiàn)單鏈表基本操作方法
這篇文章主要介紹了???????C語(yǔ)言實(shí)現(xiàn)單鏈表基本操作方法，文章圍繞主題展開詳細(xì)介紹，具有一定的參考價(jià)值，需要的小伙伴可以參考一下2022-05-05
C++實(shí)現(xiàn)簡(jiǎn)單BP神經(jīng)網(wǎng)絡(luò)
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)簡(jiǎn)單BP神經(jīng)網(wǎng)絡(luò)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-05-05
C++11用兩個(gè)線程輪流打印整數(shù)的實(shí)現(xiàn)方法
這篇文章主要介紹了C++11用兩個(gè)線程輪流打印整數(shù)的實(shí)現(xiàn)方法,本文通過實(shí)例代碼給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2020-09-09
埃拉托斯特尼篩法，簡(jiǎn)稱埃氏篩或愛氏篩，是一種由希臘數(shù)學(xué)家埃拉托斯特尼所提出的一種簡(jiǎn)單檢定素?cái)?shù)的算法。本文將利用這一算法實(shí)現(xiàn)求解素?cái)?shù)，感興趣的可以了解一下2023-01-01
大家注意不要在頭文件中定義變量，在頭文件中聲明變量。定義放在對(duì)應(yīng)的源文件中。其他地方只能用extern聲明2013-10-10