#include
#define Bag 0
int n;
int x[999];
int bestx[999];
int cp ;
int cw ;
int mw ;
int bestp ;
int c;
int w[999];
int p[999];
bool place(int t);
void Knapsack(int t);
int Shuru();
int Shuchu();
int Shuru()
{
int i;
printf("请输入背包的容量:");
scanf("%d",&c);
printf("请依次输入物品的重量:");
for(i=0;i
scanf("%d",(w+i));
printf("请依次输入物品的价值:");
for(i=0;i
scanf("%d",(p+i));
return Bag;
}
int Shuchu()
{
printf("选择的物品是:");
for(int j = 0;j
printf("%d ",bestx[j]);
printf("\n最大价值为:%d\n",bestp);
return Bag;
}
void Init();
void Init()
{
int i;
for(i = 0;i
{
x[i] = 0;
bestx[i] = 0;
w[i] = 0;
p[i] = 0;
}
}
bool place(int t)
{
if(cw+w[t] > c)
return false;
return true;
}
void Knapsack(int t)
{
int j;
if(t>=n)
{
if(cp>bestp)
{
bestp=cp;
for(j= 0;j
bestx[j] = x[j];
}
}
else
{
for(j= 0;j<=1;j++)
{
x[t] = j;
if(x[t] == 0)
{
Knapsack(t+1);
x[t] = 0;
}
else if(place(t) && x[t]==1)
{
cp = cp + p[t];
cw = cw + w[t];
Knapsack(t+1);
x[t] = 0;
cp = cp - p[t];
cw = cw - w[t];
}
}
}
}
int main()
{
Init();
printf("请输入物品的数量:");
scanf("%d",&n);
Shuru();
Knapsack(0);
Shuchu();
}