求解0/1背包问题

//求解0_1背包问题 
//动态规划
#include<stdio.h>
#define MaxN 20
#define MaxW 100
int knap(int f[MaxN][MaxW],int w[],int v[],int W,int n){
	//动态规划求数组f[][] 
	int i,r;
	for(i=0;i<=n;i++)
		f[i][0] = 0;
	for(r=0;r<=W;r++)
		f[0][r] = 0;
		
	for(i=1;i<=n;i++){
		for(r=1;r<=W;r++){
			if(r < w[i])
				f[i][r] = f[i-1][r];
			else{
				if(f[i-1][r] < f[i-1][r-w[i]] + v[i])
					f[i][r] = f[i-1][r-w[i]] + v[i];
				else
					f[i][r] = f[i-1][r];
			}
		} 
	} 
	return f[n][W]; 
}

int Traceback(int f[MaxN][MaxW],int w[],int x[],int W,int n){
	int i,r=W;
	int maxw = 0;
	for(i=n;i>0;i--){
		if(f[i][r] != f[i-1][r]){
			x[i] = 1;
			maxw += w[i];
			r = r - maxw;
		}
		else
			x[i] = 0; 
	}
	return maxw;
} 
void dispknap(int x[],int maxw,int maxv,int n){
	int i;
	printf("最佳背包方案是：\n");
	for(i=0;i<=n;i++){
		if(x[i] == 1)
			printf("选取第%d种物品\n",i); 
	}
	printf("总重量=%d,总价值=%d",maxw,maxv);
}
int main(){
	int f[MaxN][MaxW];
	int x[MaxN];
	int maxv;
	int maxw;
	int n=5,W=10;
	int w[MaxN] = {0,2,2,6,5,4};
	int v[MaxN] = {0,6,3,5,4,6};
	maxv = knap(f,w,v,W,n);
	maxw = Traceback(f,w,x,W,n);
	dispknap(x,maxw,maxv,n);
	return 0;
} 

#include<stdio.h>
#define MAXN 20
int maxw;
int maxv;
int x[MAXN];
void knap(int w[],int v[],int W,int n,int i,int tw,int tv,int op[]){
	int j;
	if(i>n){
		if(tw<W && tv>maxv){
			maxv = tv;
			maxw = tw;
			for(j=1;j<=n;j++)
				x[j] = op[j];
		}
	}
	else{
		op[i] = 1;
		knap(w,v,W,n,i+1,tw+w[i],tv+v[i],op);
		op[i] = 0;
		knap(w,v,W,n,i+1,tw,tv,op);
	}
}
void disp(int x[],int n){
	int i;
	printf("最佳方案是:\n");
	for(i=1;i<=n;i++){
		if(x[i] == 1)
			printf("选取第%d个物品\n",i);
	}
	printf("总重量 = %d,总价值 = %d",maxw,maxv);
}
int main(){
	int n=4;
	int W = 7;
	int op[MAXN];
	int w[] = {0,5,3,2,1};
	int v[] = {0,4,4,3,1};
	knap(w,v,W,n,1,0,0,op);
	disp(x,n);
        return 0;
} 

void knap(int w[],int v[],int W,int n,int i,int tw,int tv,int op[]){
	int j;
	if(i>n){
		if(tw<W && tv>maxv){
			maxv = tv;
			maxw = tw;
			for(j=1;j<=n;j++)
				x[j] = op[j];
		}
	}
	else{
		if(tw+w[i] < W)
		{
			op[i] = 1;
			knap(w,v,W,n,i+1,tw+w[i],tv+v[i],op);
		}
		op[i] = 0;
		knap(w,v,W,n,i+1,tw,tv,op);
	}
}

void knap(int w[],int v[],int W,int n,int i,int tw,int tv,int op[]){
	int j,m;
	if(i>n){
		if(tw<W && tv>maxv){
			maxv = tv;
			maxw = tw;
			for(j=1;j<=n;j++)
				x[j] = op[j];
		}
	}
	else{
		if(tw+w[i] < W)
		{
			op[i] = 1;
			knap(w,v,W,n,i+1,tw+w[i],tv+v[i],op);
		}
		op[i] = 0;
		m=0;
		for(j=0;j<i;j++)
			if(op[j] == 0)	m++;
		if(m<=1) 
			knap(w,v,W,n,i+1,tw,tv,op);
	}
}