求解分数背包问题时遇operator+匹配错误，求解决方法

Let's break down the issues in your code and fix them step by step, starting with the compile error you're seeing.

First, let's address the immediate error:

error: no match for ‘operator+’ (operand types are ‘std::vector’ and ‘int’)

This happens because you're trying to add an integer to a std::vector<int> with values = values + a * *it; — vectors don't support this operation, and more importantly, this line doesn't align with the logic of the fractional knapsack problem. You don't need to modify the values vector; instead, you should be accumulating the total value of the items you've taken into the value variable.

Beyond this compile error, there are several logical flaws in the code that would prevent it from correctly calculating the optimal loot value. Let's fix those too:

Key Issues & Fixes #

• Integer division for ratios: Your ratio vector is of type int, so values[i]/weights[i] uses integer division (truncating decimals). For fractional knapsack, we need precise floating-point ratios (e.g., 3/2 should be 1.5, not 1). Change ratio to vector<double>.
• Incorrect calculation of a: The variable a should represent the maximum amount of the highest-value-per-weight item we can take, which is the minimum of the remaining capacity and the item's weight. Your current code compares capacity to a ratio value (not weight) using std::max, which is completely wrong.
• Missing item index tracking: std::max_element gives you an iterator to the highest ratio, but you need the index of that item to access its corresponding weight and value.
• Unupdated total value: Your value variable stays at 0.0 the whole time — you need to add the value of the portion of the item you take to it.
• No item usage tracking: Once you take all of an item, you need to mark it as used so it's not selected again in future iterations.

Corrected Code #

#include <iostream>
#include <vector>
#include <algorithm>
using std::vector;

double get_optimal_value(int capacity, vector<int> weights, vector<int> values) {
    double value = 0.0;
    int n = values.size();
    vector<double> ratio(n);
    
    // Calculate value/weight ratios with floating-point precision
    for (int i = 0; i < n; ++i) {
        ratio[i] = static_cast<double>(values[i]) / weights[i];
    }
    
    while (capacity > 0) {
        // Find the iterator to the highest remaining ratio
        auto max_ratio_it = std::max_element(ratio.begin(), ratio.end());
        int index = std::distance(ratio.begin(), max_ratio_it);
        
        // Exit loop if no more valuable items are left
        if (*max_ratio_it == 0) {
            break;
        }
        
        // Take as much as possible of this item (up to remaining capacity)
        int a = std::min(capacity, weights[index]);
        
        // Add the value of this portion to the total
        value += a * ratio[index];
        
        // Reduce remaining capacity
        capacity -= a;
        
        // Mark the item as fully used by setting its ratio to 0
        ratio[index] = 0;
    }
    
    return value;
}

// Example main function to test the solution
int main() {
    int n, capacity;
    std::cin >> n >> capacity;
    vector<int> values(n);
    vector<int> weights(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> values[i] >> weights[i];
    }
    double optimal_value = get_optimal_value(capacity, weights, values);
    std::cout.precision(10);
    std::cout << optimal_value << std::endl;
    return 0;
}

Critical Change Explanations #

1. Floating-point ratios: Casting values[i] to double before division ensures we get precise fractional ratios, which is essential for choosing the most valuable items first.
2. Item index lookup: Using std::distance converts the iterator from max_element into an index, letting us access the corresponding weight of the highest-value item.
3. Correct a calculation: std::min(capacity, weights[index]) ensures we take as much of the item as possible without exceeding the remaining knapsack capacity.
4. Total value accumulation: We add a * ratio[index] to value — this is the exact value of the portion of the item we're taking.
5. Marking items as used: Setting ratio[index] = 0 ensures this item won't be selected again once we've taken all of it.

内容的提问来源于stack exchange，提问作者Hitan Elo