背包.cpp

来自「有N件物品和一个容量为V的背包。第i件物品的费用是c」· C++ 代码 · 共 54 行

#include <stdio.h>

void search(int);
void checkmax();
int w[10],v[10];         //w[i]、v[i]：第i件物品的重量和价值
int a[10],max=0;         //a数组存放当前解各物品选取情况；max：记录最大价值
int c,n;                 //c：背包容量；n：物品数量
int main()
{
	int i;
	while(1)
	{
		scanf("%d %d",&n,&c);
		if(n==0&&c==0)  break;
		for(i=0;i<n;i++)
		{
			scanf("%d",&w[i]);
		}
		for(i=0;i<n;i++)
		{	scanf("%d",&v[i]);
		}
		search(0);           //递归搜索
		printf("%d\n",max);
		max=0;
	}
}
void search(int m)
{
	if(m>=n)
		checkmax();   //检查当前解是否是可行解，若是则把它的价值与max比较
	else
	{
		a[m]=0;       //不选第m件物品
		search(m+1);  //递归搜索下一件物品
		a[m]=1;       //不选第m件物品
		search(m+1);  //递归搜索下一件物品
	}
}
void checkmax()
{
	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
			max=value;               //替换max
}