算法设计4章5章部分答案.cpp

《计算机算法设计与分析》王晓东版本第四章五章课后习题的部分答案

//算法分析题4-1
设待安排的11个活动的开始时间和结束时间按结束时间的非减序排列如下：
I	1	2	3	4	5	6	7	8	9	10	11	
s[i]	1	3	0	5	3	5	6	8	8	2	12	
f[i]	4	5	6	7	8	9	10	11	12	13	14	
最优解为：1，4，8，11
①若选择具有最短时间的相容活动作为贪心选择，得到的解为：2，4，11
②若选择覆盖未选择活动最少的相容活动作为贪心选择，得到的解为：11
显然，以上两种情况得到的解都不是最优解，故它们都不是最好的贪心选择方案。


//算法分析题4-2
首先按物品的重量从小到大排序。贪心选择性质说的就是每次都是都是选取当前的最优值。
假设背包问题每次都是从重量最小的物品开始选择的，那他一定满足贪心选择性质，
假设背包问题不是从重量最小的物品开始选择的，那么说明重量最小的物品没有装入，
现在我们用这个重量最小的物品代替当前选择装入的物品，依然可以得到一个最优解
（装入的物品的个数相同）。所以背包问题具有贪心选择性质。
http://202.115.53.252/homework


// 算法实现题4-5:
// 最短程序优先

int greedy(vector<int> x, int m)
{
	int i = 0, sum=0, n=x.size();
	sort(x.begin(),x.edd());
	while(i<n){
	sum+=x[i];
	if(sum<=m)i++;
	else return i;
	}
	return n;
}

//算法实现题4-9
//最远加油站优先


int greedy(vector<int> x, int n)
{
	int sum=0, k=x.size();
	for(int j=0;j<k;j++)
		if(x[j]>n){
			cout<<"No solution"<<endl;
			return-1;
		}
		for(int i=0;s=0;i<k;i++){
			s=s+x[i];
			if(s>n) {
				sum++;
				s=x[i];
			}
		}
	return sum;
}


//算法实现题4-12
//删数问题
//最近下降点优先

void delek()
{
	int m=a.size();
	if(k>=m){
		a.erase();
		return:
	}
	while(k>0){
		for(int i=0;(i<a.size()-1) && (a[i]<=a[i+1]);i++):
		a,erase(i,1);
		k--;
	}
	while(a.size()>1 && a[0]=='0')a.erase(0,1);
}


//算法实现题5-1
//子集和问题
//回溯法解决

template<class T>
bool Subsum<T>::backtrack(int i)
{
	if(i>n){
		for(int j=1; j<=n; j++) bestx[j]=x[j];
		bestw=cw;
		if(bestw==c)return true;
		else return false;
	}
	r-=w[i];
	if(cw+w[i]<=c){
		x[i]=1;
		cw+=w[i];
		if(backtrack(i+1))return true;
		cw-=w[i];
	}
	if(cw+r>bestw) {
		x[i]=0;
		if(backtrack(i+1)) return true;
	}
	r=r+w[i];
	return false;
}


//算法实现题5-13
//工作分配问题
//用搜索排列树的回溯法框架解决

void job::Backtrack(int t)
{
	if(t>n) Compute();  //Compute() 计算当前方案的费用
	else
		for(int j=t;j<=n;j++){
			swap(r[t],r[j]);
			Backtrack(t+1);
			swap(r[t],r[j]);
		}
}

void job::Compute(void)
{
	for(int i=1; temp=0;i<=n;i++)
		temp+=p[i][r[i]];
	if(temp<best){
		best = temp;
		for(int i=1;i<==n;i++)bestr[i]=r[i];
	}
}