0-1 背包问题（浮点数）
0-1 背包问题，一共 n < 20 个物品，每个物品价格 p[i] （浮点数），重量 w[i] （浮点数），背包容量 M （浮点数）。求最大能装的价值是多少？
输入：20 678.9123.56 51.5631.45 23.5662.54 45.6215.32 42.2312.32 65.3265.12 32.4515.65 45.7862.15 98.3232.15 45.6215.44 95.3245.65 99.4532.15 22.4823.56 51.5631.45 23.5662.54 45.6215.32 42.2312.32 65.3265.12 32.4515.65 45.7862.15 98.32输出：1050.07
题解
因为这里全部都是浮点数，所以没有办法直接用普通的动态规划来做，这里我提供几个思路。
方法1：
如果小数点只有两位的话，很简单，所有数字统一乘以 100 ，那么就都变成整数了。然后就可以直接用普通的 0-1 背包方法来做。
代码
typedeflonglongll;constintmod=1e9+7;constintN=22; structnode { doublew, p; booloperator< (constnode&rhs) const { returnw<rhs.w; }} a[1<<N], b[1<<N]; intmain() { intn; doubleM; scanf("%d%lf", &n, &M); printf("%f\n", M); vector<double>w(n, 0), p(n, 0); for (inti=0; i<n; ++i) { scanf("%lf%lf", &w[i], &p[i]); } printf("%f\n", tmp); intca=0, cb=0; for (ints=0; s< (1<<(n/2)); ++s) { doubletot_w=0, tot_p=0; for (inti=0; i<n/2; ++i) { if (s&(1<<i)) { tot_w+=w[i]; tot_p+=p[i]; if (tot_w>M) break; } } if (tot_w<=M) { a[ca].w=tot_w; a[ca].p=tot_p; ca++; } } for (ints=0; s< (1<<(n-n/2)); ++s) { doubletot_w=0, tot_p=0; for (inti=0; i<n-n/2; ++i) { if (s&(1<<i)) { tot_w+=w[n/2+i]; tot_p+=p[n/2+i]; if (tot_w>M) break; } } if (tot_w<=M) { b[cb].w=tot_w; b[cb].p=tot_p; cb++; } } sort(a, a+ca); sort(b, b+cb); vector<double>maxp(cb, 0); maxp[0] =b[0].p; for (inti=1; i<cb; ++i) { maxp[i] =max(maxp[i-1], b[i].p); } intj=cb-1; doubleres=0; for (inti=0; i<ca; ++i) { while (j>=0&&a[i].w+b[j].w>M) --j; if (j<0) break; res=max(res, a[i].p+maxp[j]); } printf("%f\n", res); return0; }
最小长度子数组
给一个正数数组，找出最小长度连续子数组，其和大于等于 m。
题解
代码
intmain() { intn, m; scanf("%d%d", &n, &m); vector<int>a(n, 0); for (inti=0; i<n; ++i) { scanf("%d", &a[i]); } intj=0, sum=0, res=INT_MAX; for (inti=0; i<n; ++i) { sum+=a[i]; while (sum>=m) { res=min(res, i-j+1); sum-=a[j++]; } } printf("%d\n", res); return0; }
作者简介：godweiyang，知乎同名，华东师范大学计算机系硕士在读，方向自然语言处理与深度学习。喜欢与人分享技术与知识，期待与你的进一步交流~
