stampassignment.cpp

一个以邮票分配方案为例的演示分治法算法的小程序

// StampAssignment.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"

using namespace std;
//using namespace General;

int *stamps;
int mSize;
int nSize;

bool getSolution(int *, int, int);
int *getPossibilities(int, int);
void stampAssignment();
void printSolution(int *, int);
void printSolution(int, int);
void printSolution(int *, int *, int);
void pause();
void sortStamps();

int _tmain(int argc, _TCHAR* argv[])
{
	int temp;
	cout<<"======================"<<endl;
	cout<<"数据结构实习十之题目六"<<endl;
	cout<<"======================"<<endl;
	cout<<endl;

	General::Input("请输入邮票面值的种类数目：", nSize);
	if (nSize <= 0) {
		cout<<"输入有误，改为默认值4"<<endl;
		nSize = 4;
	}

	nSize++;
	stamps = new int[nSize];
	stamps[0] = 0;

	for (int i = 1; i < nSize; i++) {
		cout<<"请输入第"<<i<<"种邮票的面值："<<flush;
		cin>>temp;
		if (temp <= 0) {
			cout<<"输入有误，改为默认值"<<i<<"！"<<endl;
			i--;
		}
		else stamps[i] = temp;
	}
	General::Input("请输入可以使用的最大邮票数：", mSize);
	if (mSize <= 0) {
		cout<<"输入有误，改为默认值5"<<endl;
		mSize = 5;
	}
	
	sortStamps();
	stampAssignment();
	pause();
	pause();
	return 0;
}

/**
 * 函数 getSolution
 * 返回值 bool型 表示当前要求的面值数目(rest)是否有组合方式
 * 参数 s int *型 存放组合方式的数组，长度为固定mSize
 * 参数 m int 型 表示当前组合方式中还有几个剩余空间
 * 参数 rest int 型 表示当前组合中尚不足的面值数
 */
bool getSolution(int *s, int m, int rest) {
	//possible存放当前可能成为组合中元素的列表，以-1表示结束
	int *possible = getPossibilities(m, rest);	
	int i = 0;

	//如果是递归到了最后一层，则判断是否正好凑足所需面值
	if (m == 0) return rest == 0;

	//对possible数组进行遍历
	while (possible[i] != -1) {
		s[mSize - m] = possible[i];
		if (getSolution(s, m - 1, rest - possible[i])) {
			delete possible;
			return true;
		}
		i++;
	}
	delete possible;
	return false;
}

/**
 * 函数getPossibilites 提取当前要求面值下所有可能成为组成元素的邮票
 * 返回值 int *型 可能集
 * 参数 m int型 当前还剩余的可分配邮票数
 * 参数 rest int型 当前要求的面值
 */
int *getPossibilities(int m, int rest) {
	int *p = new int[nSize + 1];
	int j = 0;
	for (int i = 0; i < nSize; i++)
		//如果当前邮票可能成为组成元素，就放入p数组中
		if (stamps[i] <= rest && stamps[i] * m >= rest) p[j++] = stamps[i];
	p[j] = -1;
	return p;
}

/**
 * 函数stampAssignment 计算主体函数
 * 返回值 void型
 */
void stampAssignment() {
	if (nSize == 0 || mSize == 0) {
		cout<<"输入数据错误！"<<endl;
		pause();
		return;
	}
	int areaEnd = 0;		//当前连续区间终止点
	int areaStart = 0;		//当前连续区间起始点
	int *areaMaxStart = new int[stamps[nSize - 1] * mSize / 2];			//最大连续区间起始点
	int *areaMaxEnd = new int[stamps[nSize - 1] * mSize / 2];			//最大连续区间终止点
	int areaMaxSize = 0;	//最大连续区间长度
	int areaMaxCount = 0;	//最大连续区间数量
	
	bool isFormerValid = false;		//标志变量，记录上一个面值是否存在分配方案

	int *s = new int[nSize];	//存放分配方案的数组

	//对所有可能出现的面值进行遍历
	for (int i = stamps[1]; i <= stamps[nSize - 1] * mSize; i++) {
		//如果当前面值存在分配方案
		if (getSolution(s, mSize, i)) {
			printSolution(s, i);
			areaEnd = i;
			areaStart = areaStart == 0 ? i : areaStart;
			isFormerValid = true;
		}
		//出现没有分配方案的面值，说明一个连续区间结束，进行相关参数的调整，并打印连续区间
		else if (isFormerValid || i == stamps[nSize - 1] * mSize) {
			printSolution(areaStart, areaEnd);
			if (areaEnd - areaStart + 1 == areaMaxSize) {
				areaMaxStart[areaMaxCount] = areaStart;
				areaMaxEnd[areaMaxCount] = areaEnd;
				areaMaxCount++;
			}
			else if (areaEnd - areaStart + 1 > areaMaxSize) {
				delete areaMaxStart;
				delete areaMaxEnd;
				areaMaxStart = new int[stamps[nSize - 1] * mSize / 2];
				areaMaxEnd = new int[stamps[nSize - 1] * mSize / 2];
				areaMaxCount = 0;
				areaMaxStart[areaMaxCount] = areaStart;
				areaMaxEnd[areaMaxCount] = areaEnd;
				areaMaxCount++;
				areaMaxSize = areaEnd - areaStart + 1;
			}
			areaStart = 0;
			areaEnd = 0;
			isFormerValid = false;
		}
	}

	//打印最终最大连续区间
	printSolution(areaMaxStart, areaMaxEnd, areaMaxCount);
}

//printSolution重载一：打印当前面值分配方案
void printSolution(int *s, int m) {
	cout<<"需求面值："<<m<<'\t';
	cout<<"分配方法：";
	for (int i = 0; i < mSize; i++) 
		if (s[i] != 0) cout<<s[i]<<'\t';
	cout<<endl;
}

//printSolution重载二：打印当前连续空间
void printSolution(int areaStart, int areaEnd) {
	cout<<"\n连续空间："<<areaStart<<"-"<<areaEnd<<"\t长度："<<areaEnd - areaStart + 1<<"\n\n"<<endl;
	pause();
}

//printSolution重载三：打印最大连续空间
void printSolution(int *areaMaxStart, int *areaMaxEnd, int areaMaxCount) {
	if (areaMaxCount == 0) return;
	int areaMaxSize = areaMaxEnd[0] - areaMaxStart[0] + 1;
	cout<<"最大连续空间长度："<<areaMaxSize<<endl;
	for (int i = 0; i < areaMaxCount; i++)
		cout<<'\t'<<i + 1<<".起始点："<<areaMaxStart[i]<<"\t终止点："<<areaMaxEnd[i]<<endl;
	pause();
}

//暂停函数
void pause() {
	cout<<"                                                            按Enter键继续..."<<endl;
	getchar();
}

//将邮票面值排序
void sortStamps() {
	int i, j, temp;
	for (i = 0; i < nSize - 1; i++) {
		for (j = i + 1; j < nSize; j++) {
			if (stamps[i] > stamps[j]) {
				temp = stamps[i];
				stamps[i] = stamps[j];
				stamps[j] = temp;
			}
		}
	}
}