算法
(01背包) $O(n * 10000)$
注意到
$$ \frac{\sum a_i}{\sum b_i} = k \Leftrightarrow \sum a_i = \sum b_i * k \Leftrightarrow \sum a_i - \sum b_i * k = 0 \Leftrightarrow \sum (a_i - k * b_i) = 0 $$
所以这是个体积是 $V_i = a_i - k * b_i$,价值是 $a_i$ 的 $01$ 背包问题。
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rrep(i, n) for (int i = 1; i <= (n); ++i)
#define dsrep(i, t, s) for (int i = (t) - 1; i >= (s); --i)
using std::cin;
using std::cout;
bool chmax(int& a, int b) { if (a < b) { a = b; return 1; } return 0; }
const int N = 110;
const int M = 10010;
int a[N], b[N];
int f[M], g[M]; // f[i]表示体积为 i 的价值,g[i] 表示体积为 -i 的价值
int main() {
int n, k;
cin >> n >> k;
rrep(i, n) cin >> a[i];
rrep(i, n) cin >> b[i];
std::memset(f, -0x3f, sizeof f);
std::memset(g, -0x3f, sizeof g);
f[0] = g[0] = 0;
rrep(i, n) {
int c = a[i] - k * b[i];
if (c >= 0) {
dsrep(j, 10001, c)
chmax(f[j], f[j - c] + a[i]);
} else {
dsrep(j, 10001, -c)
chmax(g[j], g[j + c] + a[i]);
}
}
int ans = 0;
rep(i, 10001) chmax(ans, f[i] + g[i]);
cout << (ans == 0 ? -1 : ans) << '\n';
return 0;
}