算法：poj 3628 Bookshelf 2（dfs, 01背包）

算法：poj 3628 Bookshelf 2（dfs, 01背包）2014-01-10 csdn shuangde800题目大意：

有n个数字（1～100W），现在有一个数b，1<=b<=s（s为n个数字之和）。要从n 个数字中选择一些数字组合，有一写组合的数字之和x会大于等于b，求所有x中x-b最小的是多少？

思路：

刚开始看到这题，发现数字这么大，以为内存不够不能用背包。而n最大才20，所以直接用 dfs+减枝0MS过了。。。

然后用背包，开了2000W+的数组，memset初始化，果断地MLE了。。。然后看了下discuss，发现用memset会增加很多额外的内存。

于是改用for循环初始化，内存就够用了。然后就是赤裸的01背包了

后话：

这题数据水得够可以，dp开20W数组都过了，暴力2^20的复杂度也无压力过

dfs + 减枝 0MS：

#include<iostream>#include<queue>#include<cstdio>#include<cstring>#include<cmath>typedef long long int64;const int MAXN = 1000010;const int INF = 0x3f3f3f3f;int n, b;int h[25];int sum[25];int ans;void dfs（int cur, int tol）{if（cur>n+1 || ans==b）return;if（tol >= ans）return;if（tol >= b）{ans = min（tol, ans）;return ;}if（tol + sum[n] - sum[cur-1] < b）return;dfs（cur+1, tol）;dfs（cur+1, tol+h[cur]）;}int main（）{while（~scanf（"%d%d", &n, &b））{sum[0] = 0;for（int i=1; i<=n; ++i）{scanf（"%d", &h[i]）;if（i==0） sum[0]=h[i];else sum[i] = sum[i-1]+h[i];}ans = INF;dfs（1, 0）;printf（"%d
", ans-b）;}return 0;}