背包问题.cpp

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

#include<stdio.h>

int n,c;

int w[10],p[10];
int a[10],b[100],max;

void checkmax()
{
	int i,weight=0,value=0;
	for(i=0;i<n;i++)
	{
		if(a[i]==1)
		{
			weight=weight+w[i];
			value=value+p[i];
		}
	}
	if(weight<=c)
		if(value>max)
			max=value;
}

void search(int m)
{
	if(m>=n)
		checkmax();
	else
	{
		a[m]=0;
		search(m+1);
		a[m]=1;
		search(m+1);
	}
}

void main()
{
	int i,j=0;
    while(1)
	{
		scanf("%d%d",&n,&c);
		if(n!=0&&c!=0)
		{
		    for(i=0;i<n;i++)
			   scanf("%d",&w[i]);
			for(i=0;i<n;i++)
				scanf("%d",&p[i]);
			search(0);
			b[j]=max;
			max=0;
		}
		else 
			break;
		j++;
	}
	for(i=0;i<j;i++)
		printf("%d\n",b[i]);
}