0-1バックパック遡及法
549 ワード
サンプル:
5 10 2 6 2 3 6 5 5 4 4 6
5 10 2 6 2 3 6 5 5 4 4 6
#include <stdio.h>
int n,c,v[105],w[105];
int max=-1;
void dfs(int t,int temp_w,int temp_v)
{
if(t==n)
{
if(temp_w<=c && temp_v>max)
max=temp_v;
return ;
}
temp_w+=w[t];
temp_v+=v[t];
dfs(t+1,temp_w,temp_v);
temp_w-=w[t];
temp_v-=v[t];
dfs(t+1,temp_w,temp_v);
}
int main()
{
int i,j;
scanf("%d %d",&n,&c);
for(i=0;i<n;i++)
scanf("%d %d",w+i,v+i);
dfs(0,0,0);
printf("%d
",max);
return 0;
}