0-1背包.cpp

一个c语言中经典算法 有兴趣的可以仔细

#include <stdio.h>

void readdata(int n);
void search(int m,int n,int c);
void checkmax(int n,int c);
void printresult();
int w[1000],v[1000];       
int a[1000],max,m[10000];        
                  
void main()
{
	int n,c,i;
	int temp=0;
	while(1)
	{   max=0;
	    scanf("%d%d",&n,&c);
		if(n==0&&c==0)   
			break;
		temp++;
	    readdata(n);       
	    search(0,n,c);        
		m[temp-1]=max;
	}
    for(i=0;i<temp;i++)
        printf("%d\n",m[i]);
}
void search(int m,int n,int c)
{
	if(m>=n)
		checkmax(n,c);   
	else
	{
		a[m]=0;       
		search(m+1,n,c);  
		a[m]=1;       
		search(m+1,n,c);  
	}
}
void checkmax(int n,int c)
{
	int i,weight=0,value=0;
	for(i=0;i<n;i++)
	{
		if(a[i]==1)                 
		{
			weight=weight+w[i]; 
			value=value+v[i];     
		}
	}
	if(weight<=c)                 
		if(value>max)              
			max=value;            
}
void readdata(int n)
{
	int i;
	for(i=0;i<n;i++)
		scanf("%d",&w[i]);   
	for(i=0;i<n;i++)
		scanf("%d",&v[i]);   
}