poj 3628 （搜索or背包）

好久没看背包题目了！！！生疏了！！！！

这题是背包题！！！不过对于这题，解决方法还是搜索省时！！！

题意：第一行给你一个N和VV，接下来N行，每行一个数，求得是任选N个数组合求和，求组合的和大于VV而且减去VV的最小的差！！！

囧！！！

￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥

#include<stdio.h>

#include<string.h>
#include<string.h>
#define inf 999999999


int n,a[50],visit[50],flag,vv,ans;


void dfs(int id,int sum)
{
int i;
if(flag==1)
{
ans=0;
return ;
}
if(sum>=vv)
if(sum-vv<ans)
ans=sum-vv;
for(i=id;i<n;i++)
dfs(i+1,sum+a[i]);
return ;
}
int main()
{
int i;
while(scanf("%d%d",&n,&vv)!=EOF)
{
flag=0;ans=inf;
memset(visit,0,sizeof(visit));
for(i=0;i<n;i++)
scanf("%d",&a[i]);
dfs(0,0);
printf("%d ",ans);
}
return 0;

}

题目链接：http://poj.org/problem?id=3628