CodeForces - 366C

每个糖果有两个数值 $a$, $b$ ,找到子集 $S$ 使得 $\frac{\sum _{i\subseteq S} a[i]}{\sum _{i\subseteq S} b[i]}=k$ ,求 $\sum _{i\subseteq S} a[i]$ 的最大值

其实是个背包,我们可以得到 $a[i]-k*b[i]=0$ ,把 $a[i]-k*b[i]$ 作为背包容量,做 01 背包,注意统计答案时候取 $\ max\{f1[i]+f2[i]\}$
统计 $f1$, $f2$ 是因为背包容量可能为负

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5;
const int inf = 0x3f3f3f3f;
int n, k;
int a[maxn], b[maxn], f1[maxn], f2[maxn];
int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++)
        scanf("%d", &b[i]);
    for (int i = 1; i < maxn; i++)
        f1[i] = f2[i] = -inf;
    for (int i = 1; i <= n; i++)
        if (k * b[i] - a[i] >= 0)
            for (int v = 10000; v >= k * b[i] - a[i]; v--)
                f1[v] = max(f1[v], f1[v - k * b[i] + a[i]] + a[i]);
        else
            for (int v = 10000; v >= a[i] - k * b[i]; v--)
                f2[v] = max(f2[v], f2[v + k * b[i] - a[i]] + a[i]);
    int ans = 0;
    for (int i = 0; i <= 10000; i++)
        ans = max(ans, f1[i] + f2[i]);
    if (ans)
        printf("%d\n", ans);
    else
        puts("-1");
}