Fractional knapsack in C++11

I am just picking up C++11 and decided to try some algorithmic problems to get better at it. One such problem is the fractional knapsack problem which can be solved by a greedy approach. The idea is to find the most valuable item and fill it in and move on to the next one till the knapsack is filled. Partial items are allowed.

I hope this code can be reviewed for:

• Correctness

• Correct usage of C++11 features

• Code logic improvement

• Coding conventions

struct Item {
    float value;
    float size;
    uint32_t index;
};

uint32_t FillKnapsack(std::vector &Items, const uint32_t MaxCap)
{
    // sorting is done based on value/size ratio of the item
    std::sort(Items.begin(),
              Items.end(),
              [](const Item& A, const Item& B) { return (A.value/A.size) > (B.value/B.size); });

    float c = 0, v = 0;

    for (const auto& item: Items) {
        if (c + item.size = MaxCap)
            break;
    }
    return v;
}

int main()
{
    std::vector items = { { 10, 30, 0},
                                { 20, 20, 1},
                                { 30, 10, 2} };
    std::cout << FillKnapsack(items, 35) << std::endl;
    return 0;
}

Return or Output

I feel like FillKnapsack should either (a) simply tell you the max value or (b) give you the items that it used. Right now, you're returning (a) and logging, incompletely, (b). (Incomplete because if you use a fractional amount of an item, that's not indicated).

I suggest you pick one or the other. If the former, basically just drop the couts. If the latter, you'll want to return something like a:

std::vector>

or:

struct ItemWithFraction {
    Item item;
    double fraction;
};
std::vector

Avoid single-letter variables

What is c? What is v?

Move the break into the branch

We have two cases per item: either we can fit the whole item and have room to spare, or we can't. If we can't, then we break. So that can become:

for (const auto& item : Items) {
    if (capacity + item.size < MaxCap) {
        value += item.value;
        capacity += item.size;
    }
    else {
        // last little bit left
        value += (MaxCap - capacity) / item.size * item.value;
        break;
    }
}
return value;

Don't need to assign capacity in the else case either.

Take items by copy

The idea of the algorithm suggests that given this set of items, find me a value. It doesn't suggest to me that you should reorder the items I pass in just because that happens to make it easier to solve the problem. To avoid being destructive, I'd write the signature as:

uint32_t FillKnapsack(std::vector Items, const uint32_t MaxCap)

If the user doesn't care, they can always move() the items in and avoid the copy.

Naming

Typically, UpperCase naming are used for classes (e.g. Item). Functions and variables are typically either camelCase (with the first letter lower) or snake_case. So I'd prefer

fillKnapsack(std::vector items, const uint32_t maxCapacity);

and

fill_knapsack(std::vector items, const uint32_t max_capacity);

to what you have.

StackExchange Code Review Q#116714, answer score: 2