【每日算法Day 101】字节跳动 AI Lab 精选面试编程题

今天字节三面结束了，超越妹妹保佑我通过吧！今天更新两道同学之前面试 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;
}

关注公众号【算法码上来】，每日算法干货马上就来！