Knapsack Problem Variation: Fractional Knapsack
The fractional knapsack problem is a variation of the classic 0/1 knapsack problem. While the 0/1 knapsack problem only allows items to be taken or left behind completely, the fractional knapsack problem allows items to be divided into fractions with corresponding values. This means that we can take a fraction of an item, proportional to its weight.
To solve the fractional knapsack problem, we can use a greedy algorithm that takes the items with the highest value per unit weight first. This ensures that we maximize the total value of the items in the knapsack.
Let's take a look at an example implementation in C#:
xxxxxxxxxx58
}using System;public class FractionalKnapsack{ public static double GetMaximumValue(int[] weights, int[] values, int capacity) { int n = weights.Length; // Calculate the value per unit weight for each item double[] valuePerUnitWeight = new double[n]; for (int i = 0; i < n; i++) { valuePerUnitWeight[i] = (double)values[i] / weights[i]; } // Sort the items in descending order of value per unit weight Array.Sort(valuePerUnitWeight, weights, values, Comparer<double>.Create((x, y) => y.CompareTo(x))); double maxValue = 0; int currentWeight = 0; int i = 0; // Take items until the knapsack is full while (currentWeight < capacity && i < n) { if (weights[i] <= capacity - currentWeight) { // Take the entire item maxValue += values[i];OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment
