a.cpp

需对容量为c 的背包进行装载。从n 个物品中选取装入背包的物品

#include <stdio.h>     
int n,c;
int w[10], v[10];       //w[i]、v[i]：第i件物品的重量和价值
int a[10], max;        //a数组存放当前解各物品选取情况；max：记录最大价值
                    //a[i]=0表示不选第i件物品，a[i]=1表示选第i件物品

int result[100],m; //保存结果，即每次的最大价值
void readdata()
{
int i;
for(i=0;i<n;i++)
scanf("%d",&w[i]);   //读入第i件物品重量和价值
for(i=0;i<n;i++)
scanf("%d",&v[i]);
}
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;
result[m]=max;}        //替换max
}
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 printresult()
{
int i;
for(i=0;i<m;i++)
printf("%d\n",result[i]);
}


void main()
{
m=0;
scanf("%d %d",&n,&c);
while(n!=0&&c!=0)
{ 

readdata();   //读入数据
search(0);    //递归搜索
m++;
scanf("%d %d",&n,&c);
}
printresult();
}