**
一. 枚举求解方式
二. 动态规划方式求解(三维数组)
1. 解决重复求解问题
打印结果
2. 降低时间,空间复杂度(二维数组N*suma)
重新构造解的表达形式
递归求解
代码
运行结果
3. 再次降低控件复杂度(2*suma)
代码
运行结果
一. 枚举求解方式
#include<stdio.h>const int NUM = 6;int a[NUM] = { 2,5,7,10,5,2 };int b[NUM] = { 3,8,4,11,3,4 };int nowA = 0;int nowB = 0;int res = -1;int t = 0;void fun(int now) {if (now == NUM) {int tempres = nowA > nowB ? nowA : nowB;if (tempres < res || res == -1) {res = tempres;printf("%d %d\n", t++, res);}return;}//在a上工作nowA += a[now];fun(now+1);nowA -= a[now];//在b上工作nowB += b[now];fun(now+1);nowB -= b[now];}int main() {fun(0);printf("%d", res);return 0;}
• 枚举所有的可能性,获得最终结果
二. 动态规划方式求解(三维数组)
1. 解决重复求解问题
• 当前问题的最优解 , 减少一个任务之后不一定是子问题的最优解
a[NUM] = { 2,7,5,10};
b[NUM] = { 3,4,8,11};
– res = 12
a[NUM] = { 2,7,5};
b[NUM] = { 3,4,8};
– res = 4
– 由于该性质,所以要记录子问题的所有可能 , 以供原问题使用
• 构造解的表达形式 m[n][i][j] : 当有n个任务时,
– 如果m[n][i][j] =1 ,说明可以在机器A结束时间为i , 机器B结束时间为j时完成任务 , 最终耗时为 max{i,j}
• 递归求解
– m[n][i][j] = m[n-1][i-a[n]] || m[n-1][i][j-b[n]]
– 解释 : 如果n-1个任务
• 可以在A上以i-a[n] 的时间完成 , 那么如果第n个在A上进行,n个任务就可以在A上以i时间完成
• 可以在B上以j-b[n] 的时间完成 , 那么如果第n个在B上进行,n个任务就可以在B上以j时间完成
• 求解
– 原问题的解为 min{ max{i,j} | m[n][i][j] =1 且 i<=∑a 且 j<=∑b }
#include<stdio.h>const int NUM = 6;const int MAXLEN = 99;int a[NUM + 1] = { 0,2,5,7,10,5,2 };//有效下标1-NUMint b[NUM + 1] = { 0,3,8,4,11,3,4 };//有效下标1-NUMint m[NUM + 1][MAXLEN][MAXLEN] = { 0 };//最高维度有效下标1-NUMint max(int a, int b) {return a > b ? a : b;}int main() {int suma = 0;int sumb = 0;int res = _CRT_MAXMAX;//递归表1 2 维度大小for (int i = 1; i <= NUM; i++) {suma += a[i];sumb += b[i];}//一个任务时候的基础解m[1][a[1]][0] = 1;// 第一个任务在 A上用a[1]完成,B上0完成m[1][0][b[1]] = 1;// 第一个任务在 A用0完成, B上b[1]完成//动态规划算法for (int x = 2; x <= NUM; x++) {for (int i = 0; i <= suma; i++) {for (int j = 0; j <= sumb; j++) {/*如果n-1个任务可以在A上以i-a[n] 的时间完成 , 那么如果第n个在A上进行,n个任务就可以在A上以i时间完成如果n-1个任务可以在B上以j-b[n] 的时间完成 , 那么如果第n个在B上进行,n个任务就可以在B上以j时间完成*/if ((i - a[x] >= 0 && m[x - 1][i - a[x]][j] == 1) || (j - b[x] >= 0 && m[x - 1][i][j - b[x]] == 1)) {m[x][i][j] = 1;}}}}//找到最优解for (int i = 0; i <= suma; i++) {for (int j = 0; j <= sumb; j++) {if (m[NUM][i][j] == 1 && res > max(i, j)) {res = max(i, j);}}}//输出最优解printf("%d", res);return 0;}打印结果
-
2.
-
3.
-
4.
-
5.
-
6.
-
2. 降低时间,空间复杂度(二维数组N*suma)
• 观察结果表有 :
– 若当前为完成前k个作业所的结果表,
– 对于一个在该表中可能的结果 ,
• 其所在位置的行下标表示表示产生该结果时A的完成时间
• 其所在位置的列下标表示表示产生该结果时B的完成时间
– 观察表有 , 同一个行可能会有多个结果 , 即当A可以再某个时间完成时 , B可能有多重可能的完成结果 ,由于目标解释最短时间 , 所以可以只考虑每一行最左边的解, 该行其余的解一定不会产生目标解
– 右以上结论可以得出 , 对于每一行只需要存储一个结果
重新构造解的表达形式
• 定义m[x][i] : 当执行x个任务时 , 当机器A需要i时间,时候机器B所需要的最少时间
递归求解
• 基础解 :
– 当有一个任务时候 :
• m[1][a[1]] = 0 当第一个任务在A上运行 , a[1] 时刻A执行完毕, 对应B的时间为0
• m[1][0] = b[1] 当第一个任务在B上运行,0时刻A执行完毕,对应B的执行完毕事件为b[1]
• 初始化
– 令m[][] 数组中的所有元素均为最大值MAX
– 令m[1][a[1]]=0, m[1][0] = b[1]
• 递归式
m[x][i] = min{
m[x-1][i-a[x]] (i-a[i]>=0 且 m[x-1][i-a[x]!=MAX) ,
m[x-1][i] (m[x-1][i]!=MAX)
| i∈[1,suma]
}
if (i - a[x] >= 0 && m[x - 1][i - a[x]]<m[x][i]) {
m[x][i] = m[x - 1][i - a[x]];
}
/*
要使x个任务在i时刻完成, 如果第x个任务在A上运行 , 则x-1个任务在A上运行完成的时间保证为i-a[x-1]
则x个任务运行完成时,B完成的时间和x-1个任务完成时B完成的时间m[x-1][i-a[x]]一样
如果原来X个任务在B上完成的时间m[x][i] 大于 m[x-1][i-a[x]]
则更新m[x][i] = m[x-1][i-a[x]]
*/
if (m[x - 1][i] != MAX && m[x][i] > m[x - 1][i] + b[x]) {
m[x][i] = m[x - 1][i] + b[x];
}
/*
若果x个任务在i时刻完成,且A的完成内时间为i,则但X个任务完成时间为i时 ,任务x只可以在B上运行
此时X个任务完成时B上的完成时间为 m[x-1][i] + b[x]
如果原来X个任务在B上完成的时间m[x][i] 大于 m[x-1][i]+b[x]
则更新m[x][i] = m[x-1][i]+b[x]
*/
• 原问题的解 : min{ max{mn\ , i} | i ∈[0,suma] }
代码
#include<stdio.h>
const int NUM = 6;
const int MAXLEN = 99;
int a[NUM + 1] = { 0,2,5,7,10,5,2 };//有效下标1-NUM
int b[NUM + 1] = { 0,3,8,4,11,3,4 };//有效下标1-NUM
int m[NUM + 1][MAXLEN] = {0};//最高维度有效下标1-NUM
int MAX = 0xFFFF;
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 suma = 0;
int sumb = 0;
int res = MAX;
//递归表1 2 维度大小
for (int i = 1; i <= NUM; i++) {
suma += a[i];
}
//初始化
for (int i = 0; i <= NUM; i++) {
for (int j = 0; j <= suma; j++) {
m[i][j] = MAX;
}
}
m[1][a[1]] = 0;//可以在A上运行第一个任务
m[1][0] = b[1];//在B上运行第一个任务
//动态规划算法
for (int x = 2; x <= NUM; x++) {
for (int i = 0; i <= suma; i++) {
//判断x-1个任务是否可以在A的时间为i-a[i]时间完成 对应B的时间比原来的小 , 则可以在A上运行
if (i - a[x] >= 0 && m[x - 1][i - a[x]]<m[x][i]) {
m[x][i] = m[x - 1][i - a[x]];
printf("A %d : (%2d , %2d)\n", x, i, m[x][i]);
}
////如果x-1个任务在i时间完成 , 且在B上运行第x个任务后时间小于之前的时间
if (m[x - 1][i] != MAX && m[x][i] > m[x - 1][i] + b[x]) {
m[x][i] = m[x - 1][i] + b[x];
printf("B %d : (%2d , %2d)\n", x, i, m[x][i]);
}
}
}
//找到最优解
for (int j = 0; j <= suma; j++) {
if ( res > max(m[NUM][j], j)) {
res = max(m[NUM][j], j);
}
}
printf("%d", res);
return 0;
}
运行结果
3. 再次降低控件复杂度(2*suma)
• 由于m[x][suma] 只和 m[x-1][suma] 有关, 所以不需要n行suma列的数组 , 而是只需要一个m[2][suma] 大小的数组即可
代码
#include<stdio.h>
const int NUM = 6;
const int MAXLEN = 99;
int a[NUM + 1] = { 0,2,5,7,10,5,2 };//有效下标1-NUM
int b[NUM + 1] = { 0,3,8,4,11,3,4 };//有效下标1-NUM
int m[2][MAXLEN] = {0};
int MAX = 0xFFFF;
int max(int a, int b) {
return a > b ? a : b;
}
int min(int a, int b) {
return a < b ? a : b;
}
void copyANDreset(int m[2][MAXLEN], int suma) {
for (int t = 0; t <= suma; t++) {
//复制第二行到第一行
m[0][t] = m[1][t];
//重置第二行
m[1][t] = MAX;
}
}
int main() {
int suma = 0;
int sumb = 0;
int res = MAX;
//递归表1 2 维度大小
for (int i = 1; i <= NUM; i++) {
suma += a[i];
}
//初始化
for (int i = 0; i <2; i++) {
for (int j = 0; j <= suma; j++) {
m[i][j] = MAX;
}
}
m[0][a[1]] = 0;//可以在A上运行第一个任务
m[0][0] = b[1];//在B上运行第一个任务
//动态规划算法
for (int x = 2; x <= NUM; x++) {
for (int i = 0; i <= suma; i++) {
if (i - a[x] >= 0 && m[0][i - a[x]]<m[1][i]) {
m[1][i] = m[0][i - a[x]];
}
if (m[0][i] != MAX && m[1][i] > m[0][i] + b[x]) {
m[1][i] = m[0][i] + b[x];
}
}
copyANDreset(m, suma);
}
//找到最优解
for (int j = 0; j <= suma; j++) {
if ( res > max(m[0][j], j)) {
res = max(m[0][j], j);
}
}
printf("%d", res);
return 0;
}
运行结果
• 
-
若有收获，就点个赞吧
0 人点赞
