Fractional Knapsack

#include <stdio.h>
#include <stdlib.h>

// Each item has a value and a weight.
typedef struct {
    int value;
    int weight;
} Item;

// Compare two items by ratio, highest ratio first.
int compareByRatio(const void *a, const void *b) {
    Item *x = (Item *)a;
    Item *y = (Item *)b;
    double r1 = (double)x->value / x->weight;
    double r2 = (double)y->value / y->weight;
    if (r1 < r2) return 1;   // y should come first
    if (r1 > r2) return -1;  // x should come first
    return 0;
}

// Fill the bag greedily and return the best value.
double fractionalKnapsack(int capacity, Item items[], int n) {
    qsort(items, n, sizeof(Item), compareByRatio);

    double totalValue = 0.0;
    int spaceLeft = capacity;

    for (int i = 0; i < n; i++) {
        if (items[i].weight <= spaceLeft) {
            // Whole item fits, take it all.
            spaceLeft -= items[i].weight;
            totalValue += items[i].value;
        } else {
            // Take only the fraction that fits.
            double fraction = (double)spaceLeft / items[i].weight;
            totalValue += items[i].value * fraction;
            break; // Bag is full now.
        }
    }
    return totalValue;
}

int main() {
    Item items[] = {{60, 10}, {100, 20}, {120, 30}};
    int n = 3;
    int capacity = 50;

    double best = fractionalKnapsack(capacity, items, n);
    printf("Maximum value in the bag: %.2f\n", best);
    return 0;
}

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

// Each item has a value and a weight.
struct Item {
    int value;
    int weight;
};

// Compare two items by ratio, highest ratio first.
bool compareByRatio(const Item &x, const Item &y) {
    double r1 = (double)x.value / x.weight;
    double r2 = (double)y.value / y.weight;
    return r1 > r2;
}

// Fill the bag greedily and return the best value.
double fractionalKnapsack(int capacity, vector<Item> &items) {
    sort(items.begin(), items.end(), compareByRatio);

    double totalValue = 0.0;
    int spaceLeft = capacity;

    for (const Item &it : items) {
        if (it.weight <= spaceLeft) {
            // Whole item fits, take it all.
            spaceLeft -= it.weight;
            totalValue += it.value;
        } else {
            // Take only the fraction that fits.
            double fraction = (double)spaceLeft / it.weight;
            totalValue += it.value * fraction;
            break; // Bag is full now.
        }
    }
    return totalValue;
}

int main() {
    vector<Item> items = {{60, 10}, {100, 20}, {120, 30}};
    int capacity = 50;

    double best = fractionalKnapsack(capacity, items);
    cout.setf(ios::fixed);
    cout.precision(2);
    cout << "Maximum value in the bag: " << best << endl;
    return 0;
}

import java.util.Arrays;
import java.util.Comparator;

public class FractionalKnapsack {

    // Each item has a value and a weight.
    static class Item {
        int value;
        int weight;
        Item(int value, int weight) {
            this.value = value;
            this.weight = weight;
        }
    }

    // Fill the bag greedily and return the best value.
    static double fractionalKnapsack(int capacity, Item[] items) {
        // Sort by ratio, highest ratio first.
        Arrays.sort(items, Comparator.comparingDouble(
                (Item it) -> (double) it.value / it.weight).reversed());

        double totalValue = 0.0;
        int spaceLeft = capacity;

        for (Item it : items) {
            if (it.weight <= spaceLeft) {
                // Whole item fits, take it all.
                spaceLeft -= it.weight;
                totalValue += it.value;
            } else {
                // Take only the fraction that fits.
                double fraction = (double) spaceLeft / it.weight;
                totalValue += it.value * fraction;
                break; // Bag is full now.
            }
        }
        return totalValue;
    }

    public static void main(String[] args) {
        Item[] items = {
            new Item(60, 10),
            new Item(100, 20),
            new Item(120, 30)
        };
        int capacity = 50;

        double best = fractionalKnapsack(capacity, items);
        System.out.printf("Maximum value in the bag: %.2f%n", best);
    }
}

def fractional_knapsack(capacity, items):
    # items is a list of (value, weight) pairs.
    # Sort by ratio value / weight, highest first.
    items.sort(key=lambda it: it[0] / it[1], reverse=True)

    total_value = 0.0
    space_left = capacity

    for value, weight in items:
        if weight <= space_left:
            # Whole item fits, take it all.
            space_left -= weight
            total_value += value
        else:
            # Take only the fraction that fits.
            fraction = space_left / weight
            total_value += value * fraction
            break  # Bag is full now.

    return total_value


items = [(60, 10), (100, 20), (120, 30)]
capacity = 50

best = fractional_knapsack(capacity, items)
print(f"Maximum value in the bag: {best:.2f}")

function fractionalKnapsack(capacity, items) {
  // items is an array of { value, weight } objects.
  // Sort by ratio value / weight, highest first.
  items.sort((a, b) => b.value / b.weight - a.value / a.weight);

  let totalValue = 0.0;
  let spaceLeft = capacity;

  for (const it of items) {
    if (it.weight <= spaceLeft) {
      // Whole item fits, take it all.
      spaceLeft -= it.weight;
      totalValue += it.value;
    } else {
      // Take only the fraction that fits.
      const fraction = spaceLeft / it.weight;
      totalValue += it.value * fraction;
      break; // Bag is full now.
    }
  }
  return totalValue;
}

const items = [
  { value: 60, weight: 10 },
  { value: 100, weight: 20 },
  { value: 120, weight: 30 },
];
const capacity = 50;

const best = fractionalKnapsack(capacity, items);
console.log(`Maximum value in the bag: ${best.toFixed(2)}`);