双机调度算法

假设当前有两个处理机A、B，以及n个待处理的任务。第i个任务在处理处理机A上处理需要的时间为ai，在处理机B上处理的时间为bi，两个处理机可以并行处理任务，但单个处理机不能同时执行任务。要求给定n个任务及各个任务对应的ai 、bi，求得顺序完成这些任务所需要的最短时间。

ans:
动态规划算法，最重要的是找出状态转移方程。直接上答案，后续再补充做解释：

#include<stdio.h>#define min(a,b) ((a<=b)?a:b)
#define max(a,b) ((a<=b)?b:a)#define n 5         //作业
int a[n]={2,6,7,9,12};
int b[n]={2,6,7,9,12};
int dp[20][1000]; // dp[i][j]表示前i个作业中A机器花费j的时候，B所花的时间int main(void) {int sum = 0;for(int i=1; i<=n; i++) {sum+=a[i];for(int j=0; j<=sum; j++) {dp[i][j]=dp[i-1][j]+b[i];if(j>=a[i]) {dp[i][j]=min(dp[i-1][j]+b[i], dp[i-1][j-a[i]]);}}}int ans = 99999;for(int i = 0; i <= sum; i++) {ans = min(ans, max(dp[n][i],i));}printf("ans = %d\n", ans);
}