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\n",ans);

}

return 0;

}

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

巴特西

poj 3628 （搜索or背包）

最新文章

热门文章