bb.c

在定时器中断中做LED的PWM输出 AT89C2051实现A/D转换的C51程序 单片机开发系统 指令系统 程序设计 定时与中断 系统扩展 接口技术 串行口

//简化背包问题的求解算法
#define N  8	//物品件数
#define W  30	//背包载重量

int	w[N]={1,9,12,6,3,20,15,5}; //物品的重量
int	in[N]; //物品放入标志
int	out[10][N]; //记录有效解(最多记录10个有效解)
int	n;	//有效解个数

void ww (int i,int cw)  reentrant //从第i件物品开始求解重量为cw的背包问题
{
	int j,k;
	if (w[i]==cw) {  //该物品正合适,求得一解
		in[i]=1; //将该物品放入背包中,求得一个有效解
		for (j=0,k=0;j<=i;j++) if (in[j]) out[n][k++]=w[j];//记录该有效解
		if (n<9) n++;	//有效解个数加一
		}
	if (i<N-1) {  //该物品重量不足,但不是最后一件.
		if (cw>w[i]) {
			in[i]=1;	//将该物品放入背包中
			ww (i+1,cw-w[i]); //在剩余的物品中按剩余的重量求解
			}
		in[i]=0;//不将该物品放入背包中,或将该物从背包中取出
		ww (i+1,cw);//在剩余的物品中按原重量求解
		}
}

void main ()
{
	int i,j;
	n=0;		//有效解个数初始化
	for (i=0;i<N;i++) {	
		in[i]=0;	//物品放入标志初始化
		for (j=0;j<N;j++) out[i][j]=0;//有效解记录初始化
		}
	ww (0,W); //求解(全部物品,空背包)
	while (1) ; //在这一行设置断点,中止程序运行,以便观察程序运行的结果 
}