poj 1018 Communication System

原题的链接：
http://acm.pku.edu.cn/JudgeOnline/problem?id=1018
   
这题用DP写了个算法，但是WA了，而且我觉得算法空间复杂度会很高。
请教了fuliang同学，他用搜索方法，有很强力的剪枝，一直不太领会
他的算法的思想，看了他写的代码，然后自己总结一下他的算法的思想。

把所有输入的设备按照bandwidth从小到大排序。从最小的bandwidth开始遍历，
依次搜索每一种设备，如果某个设备的bandwidth>=正遍历到的bandwidth，而且
该设备的price小于给定的初始price，那么保存该设备的bandwidth，该设备的price
累加，直到把这一种类的所有设备都遍历完。如果能找到符合要求的设备，那么就继续
遍历下一种类的设备，如果没有找到，就break。

这个算法包含的剪枝思想是：
遍历到某个bandwidth，这个bandwidth作为最小的bandwidth，比它小的bandwidth
都不考虑，在选择每种类型的设备的供应商时，只考虑bandwidth>=选择的bandwidth
的供应商的设备。选择了较大的bandwidth，因为有之前遍历到的bandwidth垫底，
所以总的bandwidth还是遍历到的bandwidth，所以这时候只要考虑找price最小的设备就是了。

很难精确描述出算法的思想，直接观摩fuliang同学的代码有助于理解该算法。
http://fuliang.iteye.com/blog/429100

评论

2 楼 samwalt 2009-08-05  

#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <limits>

using namespace std;

struct Device{
	int bandwidth;
	int price;
	int type;  //标记该设备的种类
};

vector<Device> d;  //设备集合
const int MAX_INT = numeric_limits<int>::max();
typedef unsigned int uint;

//剪枝函数
double prune(Device **devices, int *mi, int n){
	vector<Device>::iterator iter = d.begin();
	double bp = -1;

	while(iter != d.end()){
		int total_price = 0;
		bool flag;

		for(int i=0;i<n;i++){
			flag = false;
			int min_price = MAX_INT;
			if((*iter).type == i){
				min_price = (*iter).price;
				flag = true;
			}else{
				for(int j=0;j<mi[i];j++)
					if((devices[i][j].bandwidth >= (*iter).bandwidth) && (devices[i][j].price < min_price)){
						min_price = devices[i][j].price;
						flag = true;
					}
			}
			if(flag)
				total_price += min_price;
			else break;
		}
		if(flag){
			double temp_bp = (double)(*iter).bandwidth/total_price;
			if(temp_bp > bp)
				bp = temp_bp;
		}else break;
		iter++;
	}

	return bp;
}
bool cmp(const Device &a, const Device &b){
	return a.bandwidth < b.bandwidth;
}

int main(){
	int t;  //测试用例的数量
	cin>>t;
	while(t--){
		int n;  //设备的种数
		cin>>n;
		Device **devices = new Device*[n];  //所有制造商的所有设备

		int *mi = new int[n];  //某一种设备的制造商数量
		for(int j=0;j<n;j++){
			cin>>mi[j];
			devices[j] = new Device[mi[j]];
			for(int k=0;k<mi[j];k++){
				cin>>devices[j][k].bandwidth>>devices[j][k].price;
				devices[j][k].type = j;
				d.push_back(devices[j][k]);
			}
		}

		//设备集合按带宽从小到大排序
		sort(d.begin(), d.end(), cmp);

		printf("%.3f\n", prune(devices, mi, n));
		d.clear();
		delete[] mi;
		for(int j=0;j<n;j++)
			delete[] devices[j];
		delete[] devices;
	}
	return 0;
}

1 楼 samwalt 2009-08-04  

算法思想正确，代码中有逻辑错误，虽然AC了。