今天字节三面结束了，超越妹妹保佑我通过吧！今天更新两道同学之前面试 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 ，所以直接二进制枚举所有物品可能，然后取出重量小于背包容量，且价格最高的那一种就行了。时间复杂度 $O(n 2^n)$ ，勉强可以接受。
方法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 和最优答案比较就行了。
最终时间复杂度是 $(n/2)2^{n/2} + n \log (n/2)$ ，相比上面直接二进制枚举所有情况，大大降低了呀。
代码
#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 。最终时间复杂度是 $O(n)$ 的。
代码
#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;
}关注公众号【算法码上来】，每日算法干货马上就来！
