本文共 2663 字，大约阅读时间需要 8 分钟。
题目链接：
题目大意：
有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背包1：#include #include #include #include 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\n", ans-b); } return 0;}
#include背包2，内存更节省：#include #include #include #include #define MP make_pair#define SQ(x) ((x)*(x))using namespace std;typedef long long int64;const int MAXN = 1000010;const int INF = 0x3f3f3f3f;int n, b;int h[25];int ans;int f[20000010];int main(){ while(~scanf("%d%d", &n, &b)){ int sum = 0; for(int i=1; i<=n; ++i){ scanf("%d", &h[i]); sum += h[i]; } for(int i=0; i<=sum; ++i) f[i] = 0; for(int i=1; i<=n; ++i) for(int v=sum; v>=h[i]; --v) f[v] = max(f[v], f[v-h[i]]+h[i]); int ans = INF; for(int v=b; v<=sum; ++v) if(f[v]>=b && f[v]-b < ans) ans = Abs(f[v]-b); printf("%d\n", ans); } return 0;}
#include#include #include #include #include using namespace std;const int INF = 0x3f3f3f3f;int n, b;int h[25];int ans;bool f[20000010];int main(){ while(~scanf("%d%d", &n, &b)){ int sum = 0; for(int i=1; i<=n; ++i){ scanf("%d", &h[i]); sum += h[i]; } for(int i=1; i<=sum; ++i) f[i] = false; f[0] = true; for(int i=1; i<=n; ++i) for(int v=sum; v>=h[i]; --v) if(f[v-h[i]]) f[v] = true; int ans = INF; for(int i=b; i<=sum; ++i)if(f[i]){ printf("%d\n", i-b); break; } } return 0;}
转载地址：http://lpzni.baihongyu.com/