[ACM实验八]ACM程序设计基础（6）
杰拉斯 | 时间：2012-06-03, Sun | 19,741 views编程算法
实验项目：ACM程序设计基础(6)
实验目的：掌握C++程序设计基础。
实验要求：使用VC++6.0实现实验要求。
实验内容：
1．猜牌游戏问题，请看简单回溯——猜牌游戏（提示：可以参考实验六的最后一题Crashing Balloon）。
2. 给定n个作业的集合Jn，每一个作业Ji都有两项任务分别在2台机器上完成。每个作业必须先由机器1处理，然后再由机器2处理。求所有作业在机器2上完成处理的时间和最少，并输出最佳调度方案。如：
| 机器1 | 机器2 | |
| 作业1 | 2 | 1 |
| 作业2 | 3 | 1 |
| 作业3 | 2 | 3 |
最佳调度方案为：1 3 2，其完成时间为18。
3. 电路布线问题，请看简单动态规划——电路布线。
1.猜牌游戏问题，请看简单回溯——猜牌游戏。
2.最佳调度方案
思路是通过全排列搜索所有排序情况，并计算出结果，与当前最小值比较，最终得出答案。
难点是完成时间的计算，注意题目要求计算的是在机器二上的完成时间之和，而非所用时间之和，以上述数据为例：
| 机器1 | 机器2 | |
| 1 | 作业1（2小时） | |
| 2 | ||
| 3 | 作业3（2小时） | 作业1（1小时） |
| 4 | ||
| 5 | 作业2（3小时） | 作业3（3小时） |
| 6 | ||
| 7 | ||
| 8 | 作业2（1小时） |
可以看出3个作业的完成时间分别是3,7,8，因此完成时间之和为3 + 7 + 8 = 18。
而代码我是这么实现的：设两个变量t1与t2，分别表示当前作业在机器1与机器2上的完成时间，则：
- 当前作业在机器1上的处理只需等上一作业在机器1上完成，即t1 += 当前作业在机器1上所需的处理时间
- 当前作业在机器2上的处理必须等当前作业在机器1上完成且上一作业在机器2上完成之后开始，即：t2 = max(t1, t2) + 当前作业在机器2上所需的处理时间
代码如下：
#include<stdio.h>
#include<iostream>
using namespace std;
int min = 0xffffff;
inline int max(int a, int b){
return a > b ? a : b;
}
void Solve(int a[100][2], int b[], int n, int k){
int i;
if(k == n){
int t1 = 0, t2 = 0, sum = 0;
for(i = 0; i < n; ++i){
t1 += a[b[i]][0];
t2 = max(t1, t2) + a[b[i]][1];
sum += t2;
}
if(min > sum)
min = sum;
return;
for(i = 0; i < n; ++i){
printf("%d", b[i]);
}
printf("\n");
return;
}
for(i = k; i < n; ++i){
swap(b[i], b[k]);
Solve(a, b, n, k + 1);
swap(b[i], b[k]);
}
}
int main(){
int i, n, a[100][2], b[100];
for(i = 0; i < 100; ++i){
b[i] = i;
}
scanf("%d", &n);
for(i = 0; i < n; ++i){
scanf("%d%d", &a[i][0], &a[i][1]);
}
Solve(a, b, n, 0);
printf("%d\n", min);
return 0;
}
3. 电路布线问题，请看简单动态规划——电路布线。
如需转载请注明出处：杰拉斯的博客
int min = 0xffffff; 这个方法不错。这里是6个f，是多少位的机器？
十六进制的6个F换算成十进制是16777215，还远远小于32位int类型的最大值2147483647。