[ACM实验八]ACM程序设计基础(6)

蓝飞 蓝飞 | 时间:2012-06-03, Sun | 10,749 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. 电路布线问题,请看简单动态规划——电路布线

如需转载请注明出处:蓝飞技术部落格

2 条评论 »

  1. int min = 0xffffff; 这个方法不错。这里是6个f,是多少位的机器?

    1. 十六进制的6个F换算成十进制是16777215,还远远小于32位int类型的最大值2147483647。