c++求一组解xi(1<=i<=n,且xi=0或1) 使得∑ i=1 n ​ ai∗xi/∑ i=1 n ​ bi∗xi最大,且恰好有k个xi为1.

在C++中，这个问题可以转化为一个线性规划或者动态规划的问题。给定一组系数 \( a_i \) 和 \( b_i \)，目标是最大化 \( \sum_{i=1}^{n} \frac{a_i}{b_i} \cdot x_i \) 的值，其中约束条件是 \( x_i \) 只能取0或1，并且恰好有 k 个 \( x_i \) 等于1。这是一个典型的0-1背包问题。

我们可以采用贪心策略或者动态规划来解决。由于 \( \frac{a_i}{b_i} \) 可能会很大，一个简单的思路是优先选择较大的 \( \frac{a_i}{b_i} \) 值对应的变量设为1。这通常适用于当 \( b_i \) 非常小而 \( a_i \) 很大时，因为这将极大地增加分数。

以下是大致的算法步骤：

1. 初始化两个数组，分别存储 \( \frac{a_i}{b_i} \) 和 \( -\frac{a_i}{b_i} \) 的值，方便后续排序。
2. 对这两个数组进行降序排列。
3. 创建一个大小为 k 的布尔数组，用于记录哪些位置的 \( x_i \) 设为1。
4. 从最大的 \( \frac{a_i}{b_i} \) 开始遍历，如果当前位置还没满，将对应的 \( x_i \) 设为1并更新总和。
5. 最终得到的最大分数就是所求。

#include <vector>
#include <algorithm>

double getMaxScore(std::vector<int>& a, std::vector<int>& b, int k) {
    double ratios[] = {a[i] / b[i], -a[i] / b[i]};
    std::sort(ratios, ratios + a.size(), std::greater<double>());

    double sum = 0;
    for (int i = 0; i < k && i < a.size(); ++i) {
        if (!x[i]) {
            x[i] = 1;
            sum += ratios[i];
        }
    }

    return sum;
}

注意，这里 `x` 应该是一个大小为 n 的布尔数组，表示每个 xi 是否为1，它在这个上下文中需要预先初始化。同时，这个算法假设了存在一个可行的解（即 n >= k），否则可能无法找到满足条件的结果。