C++ Fractional Knapsack Problem Solution

What Will You Learn in This Guide?

In this guide, we will solve the Fractional Knapsack problem using C++.
You will learn to choose the items that provide the highest value, step by step, with the logic of the Greedy algorithm.
You will also discover the differences with 0/1 Knapsack, the logic of odds ordering and why this method is always optimal.

Technical Summary

• Problem: Maximizing total value in a bag with limited capacity
• Approach: Greedy
• Time Complexity: O(N log N)
• Critical Step: Sort the items in Descending order by Value/Weight ratio
• Advantage: Always the optimum solution thanks to fractional selection

---

What is Fractional Knapsack?

In this problem, each item has weight and value.
The capacity of the bag is limited to W.
The goal is to get the highest total value without exceeding the bag capacity.

Difference:

• 0/1 Knapsack → You either buy the item completely or not at all.
• Fractional Knapsack → You can get a fraction (e.g. 30%) of the item.

---

Greedy Algorithm Logic

Greedy algorithms make the best (local maximum) choice at each step.
The safe choice in this problem is to take the item with the highest value/weight ratio.

Evidence:

Starting with the most efficient (high rate) item always maximizes the total value.
Because buying a lower rate item first will always result in a lower total.

---

Step by Step Fractional Knapsack Solution

1. Calculate Ratio: Find the ratio değer / ağırlık for each item.
2. Sort: Sort the items in descending order according to this ratio (O(N log N)).
3. Fill the Bag: Take the items in the ordered list in order.
   • If the item fits buy the whole thing.
   • If it doesn't fit take the fraction, then finish the process.
4. Update Value: Increase the total value by the value of each item purchased.
5. Stop when capacity reaches 0.

---

Fractional Knapsack C++ Code

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

// Eşyaları değer/ağırlık oranına göre sıralayan karşılaştırıcı
bool compare(pair<float, int> p1, pair<float, int> p2) {
    return p1.first > p2.first;
}

// Ana çözüm fonksiyonu
float fractional_knapsack(vector<int> weights, vector<int> values, int capacity) {
    int len = weights.size();
    float total_value = 0.0;

    // (oran, orijinal_index) çiftleri
    vector<pair<float, int>> ratio(len);
    for (int i = 0; i < len; i++)
        ratio[i] = make_pair((float)values[i] / weights[i], i);

    // Oranlara göre azalan sırayla sıralama
    sort(ratio.begin(), ratio.end(), compare);

    for (int i = 0; i < len; i++) {
        if (capacity == 0) break;

        int idx = ratio[i].second;

        if (weights[idx] <= capacity) {
            capacity -= weights[idx];
            total_value += values[idx];
        } else {
            float fraction = (float)capacity / weights[idx];
            total_value += values[idx] * fraction;
            capacity = 0;
        }
    }
    return total_value;
}

int main() {
    vector<int> weights, values;
    int capacity;

    cout << "Eşya ağırlıklarını girin (-1 sonlandırır): ";
    while (true) {
        int w; cin >> w;
        if (w == -1) break;
        weights.push_back(w);
    }

    cout << "Eşya değerlerini girin (-1 sonlandırır): ";
    while (true) {
        int v; cin >> v;
        if (v == -1) break;
        values.push_back(v);
    }

    cout << "Çanta kapasitesini girin: ";
    cin >> capacity;

    cout << "\nMaksimum elde edilebilir toplam değer: "
         << fractional_knapsack(weights, values, capacity) << endl;
}

• Description: This code receives data from the user, sorts the items according to their proportions and makes fractional purchases based on the bag capacity.

---

Complexity Table

Feature	Description
Approach	Greedy
Time Complexity	O(N log N)
Space Complexity	O(N)
Advantage	Provides fast, optimal results
Limitation	Not valid for 0/1 Knapsack

---

Frequently Asked Questions (FAQ)

1. Why does Fractional Knapsack always give optimal results?

Because the possibility of fractional purchasing makes local selection safe, always providing maximum efficiency.

2. Why can't 0/1 Knapsack be solved by greedy approach?

Because fractional selection cannot be made in the 0/1 problem, so dynamic programming is required.

3. Why do we sort by value/weight ratio?

This ratio is the criterion of "providing the highest return with the least weight".

4. Why are the rate and index stored together?

To find the weight and value of the original item after sorting.

5. What is its real-world use?

Situations such as resource allocation, cloud server load balancing, investment portfolio optimization.

---

Result

In this guide, we solved the C++ Fractional Knapsack Problem step by step. We achieved high performance results thanks to the O(N log N) complexity of the Greedy algorithm.

• This is the basis of optimization in the real world:

The right small choices at every step lead to big gains.

• Test your optimization algorithms on the GenixNode platform and experience the most efficient resource planning!