數(shù)據(jù)結(jié)構(gòu) 雙機(jī)調(diào)度問(wèn)題的實(shí)例詳解
數(shù)據(jù)結(jié)構(gòu) 雙機(jī)調(diào)度問(wèn)題的實(shí)例詳解
1.問(wèn)題描述
雙機(jī)調(diào)度問(wèn)題,又稱獨(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來(lái)處理，則所需要的時(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ī)器開(kāi)工到最后一臺(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í)例，如有疑問(wèn)請(qǐng)留言或者到本站社區(qū)交流討論，感謝閱讀，希望能幫助到大家，謝謝大家對(duì)本站的支持！
相關(guān)文章
Qt實(shí)戰(zhàn)之實(shí)現(xiàn)圖片瀏覽器
這篇文章主要為大家詳細(xì)介紹了如何利用Qt實(shí)現(xiàn)簡(jiǎn)易的圖片瀏覽器，文中的示例代碼講解詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴可以了解一下2023-03-03
C++11中為了更好的支持泛型編程，提供了?auto和decltype兩個(gè)關(guān)鍵詞,目的就是提供編譯階段的自動(dòng)類型推導(dǎo)，這篇文章主要介紹了C++11中的類型推斷,需要的朋友可以參考下2023-01-01
C語(yǔ)言柔性數(shù)組的實(shí)現(xiàn)示例
柔性數(shù)組既數(shù)組大小待定的數(shù)組, C語(yǔ)言中結(jié)構(gòu)體的最后一個(gè)元素可以是大小未知的數(shù)組,本文就來(lái)介紹一下柔性數(shù)組的用法，感興趣的可以了解一下2024-03-03
C語(yǔ)言中自動(dòng)隱式轉(zhuǎn)換與類型強(qiáng)制轉(zhuǎn)換實(shí)例分析
這篇文章主要介紹了C語(yǔ)言中自動(dòng)隱式轉(zhuǎn)換與類型強(qiáng)制轉(zhuǎn)換實(shí)例分析,需要的朋友可以參考下2014-07-07
C語(yǔ)言基礎(chǔ)使用IDE快速開(kāi)發(fā)的方法
這篇文章主要介紹了C語(yǔ)言基礎(chǔ)使用IDE快速開(kāi)發(fā)的方法，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2020-11-11
這篇文章主要介紹了C++中模板(Template)的詳解及其作用介紹，本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2021-09-09
本文主要介紹C語(yǔ)言冒泡排序算法,這里給大家舉例說(shuō)明冒泡排序的思想,并附有代碼示例,有需要的小伙伴可以參考下2016-07-07
C語(yǔ)言字符串與字符數(shù)組面試題中最易錯(cuò)考點(diǎn)詳解
這篇文章主要介紹了C語(yǔ)言字符串與字符數(shù)組面試題中最易錯(cuò)考點(diǎn)，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)吧2022-09-09
用C語(yǔ)言實(shí)現(xiàn)簡(jiǎn)易通訊錄
這篇文章主要為大家詳細(xì)介紹了用C語(yǔ)言實(shí)現(xiàn)簡(jiǎn)易通訊錄，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-02-02
Qt使用Quazip解壓縮、壓縮文件的實(shí)現(xiàn)
Quazip是在zlib基礎(chǔ)上進(jìn)行了簡(jiǎn)單封裝的開(kāi)源庫(kù),利用它可以很方便將單個(gè)或多個(gè)文件打包為zip文件,本文主要介紹了Qt使用Quazip解壓縮、壓縮文件的實(shí)現(xiàn),具有一定的參考價(jià)值,感興趣的可以了解一下2023-11-11