http://blog.163.com/beachman_cy/blog/static/24949601920151122103930984/

Problem: Transportation
Description:  有一趟火车，起点是A，终点是B，现在沿途有一些站要上乘客，你可以选择让他们都上车也可不让他们上车，火车是有荷载的，车票也是一站一块钱，那么求火车从起点到终点最多能盈利多少？
Solution: DFS, 到了一个站有两种方案上或不上，分别扩展就是，这个题可以剪枝也可以不剪枝，剪枝的时间是不剪枝的1/8，建议剪枝，剪枝的方法就是如果当前的收入加上以后最大的收入小于或等于最大收入就停止搜索。很直观的剪枝。
Code(C++):(剪枝) 

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef struct tagTrain{
	int in,out;
	int number;
	int earning;
	int maxEarning;
}Train;

Train trains[25];
int singleStationPersons[10];	//每个站的人数
int maxPersons,stations,m;
int maxEarning;

int cmp(const void *a,const void *b){
	Train *A=(Train *)a;
	Train *B=(Train *)b;
	if(A->in!=B->in){
		return A->in-B->in;
	}
	return A->out-B->out;
}

void inTrain(int start,int end,int number){
	for(int i=start;i<end;i++){
		singleStationPersons[i]+=number;
	}
}

void outTrain(int start,int end,int number){
	for(int i=start;i<end;i++){
		singleStationPersons[i]-=number;
	}
}

void dfs(int nowStep,int nowEarning){
	if(nowStep==m){
		if(nowEarning>maxEarning){
			maxEarning=nowEarning;
		}
		return ;
	}

	//剪枝，如果当前收入+以后的最大收入都小于或等于最大收入，停止搜索
	if(nowEarning+trains[nowStep].maxEarning<=maxEarning){
		return ;
	}

	if(singleStationPersons[trains[nowStep].in]+trains[nowStep].number>maxPersons){
		//车的容量不够，他们上不了车
		dfs(nowStep+1,nowEarning);
	}else{
		//车的容量够，让他们上车
		inTrain(trains[nowStep].in,trains[nowStep].out,trains[nowStep].number);
		dfs(nowStep+1,nowEarning+trains[nowStep].earning);

		//车的容量够，但是不让他们上车
		outTrain(trains[nowStep].in,trains[nowStep].out,trains[nowStep].number);
		dfs(nowStep+1,nowEarning);
	}
}

int main(){
	while(scanf("%d%d%d",&maxPersons,&stations,&m),maxPersons+stations+m!=0){

		//initialize
		int sum=0;
		for(int i=0;i<m;i++){
			int in,out,number;
			scanf("%d%d%d",&in,&out,&number);
			trains[i].in=in;
			trains[i].out=out;
			trains[i].number=number;
			trains[i].earning=(out-in)*number;
		}
		qsort(trains,m,sizeof(Train),cmp);
		//求当前到以后的最大收入
		for(int i=m-1;i>=0;i--){
			sum+=trains[i].earning;
			trains[i].maxEarning=sum;
		}

		//work
		maxEarning=0;
		memset(singleStationPersons,0,sizeof(singleStationPersons));
		dfs(0,0);

		//print
		printf("%d\n",maxEarning);
	}
	return 0;
}

Code(C++): (不剪枝)

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef struct tagTrain{
	int in,out;
	int number;
	int earning;
}Train;

Train trains[25];
int singleStationPersons[10];	//每个站的人数
int maxPersons,stations,m;
int maxEarning;

int cmp(const void *a,const void *b){
	Train *A=(Train *)a;
	Train *B=(Train *)b;
	if(A->in!=B->in){
		return A->in-B->in;
	}
	return A->out-B->out;
}

void inTrain(int start,int end,int number){
	for(int i=start;i<end;i++){
		singleStationPersons[i]+=number;
	}
}

void outTrain(int start,int end,int number){
	for(int i=start;i<end;i++){
		singleStationPersons[i]-=number;
	}
}

void dfs(int nowStep,int nowEarning){
	if(nowStep==m){
		if(nowEarning>maxEarning){
			maxEarning=nowEarning;
		}
		return ;
	}

	if(singleStationPersons[trains[nowStep].in]+trains[nowStep].number>maxPersons){
		//车的容量不够，他们上不了车
		dfs(nowStep+1,nowEarning);
	}else{
		//车的容量够，让他们上车
		inTrain(trains[nowStep].in,trains[nowStep].out,trains[nowStep].number);
		dfs(nowStep+1,nowEarning+trains[nowStep].earning);

		//车的容量够，但是不让他们上车
		outTrain(trains[nowStep].in,trains[nowStep].out,trains[nowStep].number);
		dfs(nowStep+1,nowEarning);
	}
}

int main(){
	while(scanf("%d%d%d",&maxPersons,&stations,&m),maxPersons+stations+m!=0){

		//initialize
		for(int i=0;i<m;i++){
			int in,out,number;
			scanf("%d%d%d",&in,&out,&number);
			trains[i].in=in;
			trains[i].out=out;
			trains[i].number=number;
			trains[i].earning=(out-in)*number;
		}
		qsort(trains,m,sizeof(Train),cmp);
		//work
		maxEarning=0;
		memset(singleStationPersons,0,sizeof(singleStationPersons));
		dfs(0,0);

		//print
		printf("%d\n",maxEarning);
	}
	return 0;
}