#include <iostream>
#include <cmath>
#include <algorithm>
#define maxn 55
using namespace std;
int w,n,maxvalue=0,maxweight=0;
int value[maxn],weight[maxn],choice[maxn]={0},ans[maxn]={0};
void dfs(int index,int sumv,int sumw)//index是物品的下标,从1开始
{
if(index == (n+1))//完成对n个物品的选择
{
if(sumw<=w && sumv>maxvalue)//只有在可以更新最优解的时候才去更新ans[]
{
maxweight=sumw;
maxvalue=sumv;
for(int i=1;i<=n;i++)
ans[i]=choice[i];
}
return ;
}
choice[index]=0;
dfs(index+1,sumv,sumw);//不选第index个物品
if(sumw+weight[index]<=w)//只有当加入第index后重量不超过限制,才会递归
{
choice[index]=1;
dfs(index+1,sumv+value[index],sumw+weight[index]);
}
}
int main()
{
int i;
printf("请依次输入物品的数量n和限重重量w:");
scanf("%d %d",&n,&w);//输入物品个数n和限重质量w
printf("请依次输入这些物品的价值:");
for(i=1;i<=n;i++)
{
scanf("%d",&value[i]);
}
printf("请依次输入这些物品的重量:");
for(i=1;i<=n;i++)
{
scanf("%d",&weight[i]);
}
dfs(1,0,0);
printf("所选物品的最大价值之和为:%d,最大重量之和为:%d\n",maxvalue,maxweight);
for(i=1;i<=n;i++)
if(ans[i]==1)
printf("选取第%d个物品\n",i);
return 0;
}