今天字节三面结束了，超越妹妹保佑我通过吧！今天更新两道同学之前面试 AI Lab 时遇到的题。
0-1 背包问题（浮点数）
0-1 背包问题，一共 n < 20 个物品，每个物品价格 p[i] （浮点数），重量 w[i] （浮点数），背包容量 M （浮点数）。求最大能装的价值是多少？
输入： 20 678.91 23.56 51.56 31.45 23.56 62.54 45.62 15.32 42.23 12.32 65.32 65.12 32.45 15.65 45.78 62.15 98.32 32.15 45.62 15.44 95.32 45.65 99.45 32.15 22.48 23.56 51.56 31.45 23.56 62.54 45.62 15.32 42.23 12.32 65.32 65.12 32.45 15.65 45.78 62.15 98.32 输出： 1050.07
题解
因为这里全部都是浮点数，所以没有办法直接用普通的动态规划来做，这里我提供几个思路。
方法1：
如果小数点只有两位的话，很简单，所有数字统一乘以 100 ，那么就都变成整数了。然后就可以直接用普通的 0-1 背包方法来做。
方法2：
因为 n < 20 ，所以直接二进制枚举所有物品可能，然后取出重量小于背包容量，且价格最高的那一种就行了。时间复杂度 ，勉强可以接受。
方法3：
将 n 个物品平均分成两份，对每一份做二进制枚举，然后保存所有可能的总重量和对应的总价格。保存在两个数组中，记为 a 和 b ，分别表示两份的所有可能情况。
预处理出 b 中重量小于等于 b[j].w 的最大价格，保存在 maxp[j] 中。
分别按照 w 排序，然后用双指针，从重量小的开始遍历 a 中每个元素 a[i] ，在 b 中找出重量最高的那个满足 a[i].w + b[j].w 不超过背包容量的 j 。
然后 i 移动到 i+1 ，也就是重量增加了，那么 j 只能减小了，直到减小到 a[i].w + b[j].w 再次不超过背包容量。然后直接取预处理好的 maxp[j]+a[i].p 和最优答案比较就行了。
最终时间复杂度是 ，相比上面直接二进制枚举所有情况，大大降低了呀。
代码
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int mod = 1e9 + 7; const int N = 22; struct node { double w, p; bool operator < (const node& rhs) const { return w < rhs.w; } } a[1<<N], b[1<<N]; int main() { int n; double M; scanf("%d%lf", &n, &M); printf("%f\n", M); vector<double> w(n, 0), p(n, 0); for (int i = 0; i < n; ++i) { scanf("%lf%lf", &w[i], &p[i]); } printf("%f\n", tmp); int ca = 0, cb = 0; for (int s = 0; s < (1<<(n/2)); ++s) { double tot_w = 0, tot_p = 0; for (int i = 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 (int s = 0; s < (1<<(n-n/2)); ++s) { double tot_w = 0, tot_p = 0; for (int i = 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 (int i = 1; i < cb; ++i) { maxp[i] = max(maxp[i-1], b[i].p); } int j = cb-1; double res = 0; for (int i = 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); return 0; }
最小长度子数组
给一个正数数组，找出最小长度连续子数组，其和大于等于 m。
题解
这题还是用双指针，首先用 i 遍历每一个位置，然后维护 a[j] ~ a[i] 之间的元素和。如果发现和大于等于 m ，那就更新最小长度，同时增大 j 直到区间和小于 m 。最终时间复杂度是 的。
代码
#include <bits/stdc++.h> using namespace std; int main() { int n, m; scanf("%d%d", &n, &m); vector<int> a(n, 0); for (int i = 0; i < n; ++i) { scanf("%d", &a[i]); } int j = 0, sum = 0, res = INT_MAX; for (int i = 0; i < n; ++i) { sum += a[i]; while (sum >= m) { res = min(res, i-j+1); sum -= a[j++]; } } printf("%d\n", res); return 0; }
