POJ 3628 Bookshelf 2 DFS 0-1背包问题

刚刚看到我还以为是就是简单排序呢，总是WA

然后又使用二进制枚举，不过二进制还不太熟悉，用的将十进制计算转换成二进制，然后计算，总是TLE，记录一下，练习练习位操作

最后看到了递归的方法

当然本题属于背包问题，可以用DP解决

标记，学习了！

/* Author : yan
 * Question : POJ 3628 Bookshelf 2
 * Data && Time : Wednesday, December 22 2010 11:34 PM
*/
#include<stdio.h>
int cow[20];
int b;
int n;
int ans=99999999;
void DFS(int num,int sum)
{
	if(sum>=ans) return;
	if(num==n)
	{
		if(sum>=b) ans=sum;
		return;
	}
	DFS(num+1,sum);
	DFS(num+1,sum+cow[num]);
}
int main()
{
	//freopen("input","r",stdin);
	int i,j,cnt,tmp;
	int sum;
	scanf("%d %d",&n,&b);
	for(i=0;i<n;i++)
		scanf("%d",&cow[i]);
	DFS(0,0);
	printf("%d",ans-b);
	return 0;
}