Fractional Knapsack
In this page:
Problem Idea
Unlike 0-1 knapsack, the fractional knapsack problem allows taking any fraction of an item — like being able to scoop out exactly 2.5 kg of a 5 kg sack of rice instead of only taking the whole sack or nothing.
Example: Problem Idea
#include <iostream>
using namespace std;
int main() {
double weight = 5.0, take = 2.5;
cout << "Can take " << take << " kg of a " << weight << " kg sack -- fractions allowed, unlike 0-1 knapsack";
return 0;
}public class Main {
public static void main(String[] args) {
double weight = 5.0, take = 2.5;
System.out.println("Can take " + take + " kg of a " + weight + " kg sack -- fractions allowed, unlike 0-1 knapsack");
}
}weight, take = 5.0, 2.5
print(f"Can take {take} kg of a {weight} kg sack -- fractions allowed, unlike 0-1 knapsack")#include <stdio.h>
int main() {
double weight = 5.0, take = 2.5;
printf("Can take %.1f kg of a %.1f kg sack -- fractions allowed, unlike 0-1 knapsack", take, weight);
return 0;
}Login to try C/C++/Java code in the editor
Value per Weight
The key ranking metric is value divided by weight for each item; sorting items by this ratio from highest to lowest tells you which items give the most value per unit of capacity used.
Example: Value per Weight
#include <iostream>
using namespace std;
int main() {
int values[] = {60, 100, 120}, weights[] = {10, 20, 30};
for (int i = 0; i < 3; i++) cout << "ratio " << i << ": " << (double)values[i]/weights[i] << " ";
return 0;
}public class Main {
public static void main(String[] args) {
int[] values = {60, 100, 120}, weights = {10, 20, 30};
for (int i = 0; i < 3; i++) System.out.print("ratio " + i + ": " + ((double)values[i]/weights[i]) + " ");
}
}values, weights = [60, 100, 120], [10, 20, 30]
for i in range(3):
print(f"ratio {i}: {values[i]/weights[i]}", end=" ")#include <stdio.h>
int main() {
int values[] = {60, 100, 120}, weights[] = {10, 20, 30};
for (int i = 0; i < 3; i++) printf("ratio %d: %.2f ", i, (double)values[i]/weights[i]);
return 0;
}Login to try C/C++/Java code in the editor
Take Full or Part
Working down the sorted list, take as much of the current highest-ratio item as will fit; once an item doesn't fully fit in the remaining capacity, take exactly the fraction of it that does fit and stop, since nothing higher-value-per-weight remains.
Example: Take Full or Part
#include <iostream>
using namespace std;
int main() {
double capacity = 25, weights[] = {10, 20, 30}, values[] = {60, 100, 120};
double totalValue = 0;
for (int i = 0; i < 3 && capacity > 0; i++) {
double take = min(capacity, weights[i]);
totalValue += take * (values[i]/weights[i]);
capacity -= take;
}
cout << "Total value packed: " << totalValue;
return 0;
}public class Main {
public static void main(String[] args) {
double capacity = 25;
double[] weights = {10, 20, 30}, values = {60, 100, 120};
double totalValue = 0;
for (int i = 0; i < 3 && capacity > 0; i++) {
double take = Math.min(capacity, weights[i]);
totalValue += take * (values[i]/weights[i]);
capacity -= take;
}
System.out.println("Total value packed: " + totalValue);
}
}capacity = 25
weights, values = [10, 20, 30], [60, 100, 120]
total_value = 0
for i in range(3):
if capacity <= 0:
break
take = min(capacity, weights[i])
total_value += take * (values[i]/weights[i])
capacity -= take
print("Total value packed:", total_value)#include <stdio.h>
int main() {
double capacity = 25, weights[] = {10, 20, 30}, values[] = {60, 100, 120};
double totalValue = 0;
for (int i = 0; i < 3 && capacity > 0; i++) {
double take = capacity < weights[i] ? capacity : weights[i];
totalValue += take * (values[i]/weights[i]);
capacity -= take;
}
printf("Total value packed: %.2f", totalValue);
return 0;
}Login to try C/C++/Java code in the editor
Greedy Strategy
This greedy ratio-based strategy is provably optimal for the fractional version specifically because partial items are allowed — there's no risk of wasting leftover capacity the way the all-or-nothing rule in 0-1 knapsack can.
Example: Greedy Strategy
#include <iostream>
using namespace std;
int main() {
cout << "Ratio-based greedy is provably optimal here because partial items mean no capacity is ever wasted";
return 0;
}public class Main {
public static void main(String[] args) {
System.out.println("Ratio-based greedy is provably optimal here because partial items mean no capacity is ever wasted");
}
}print("Ratio-based greedy is provably optimal here because partial items mean no capacity is ever wasted")#include <stdio.h>
int main() {
printf("Ratio-based greedy is provably optimal here because partial items mean no capacity is ever wasted");
return 0;
}Login to try C/C++/Java code in the editor
Practice
Work through a few items with different weights and values by hand: compute each ratio, sort by it, and fill the knapsack greedily to see why taking the best ratio first always beats other orderings here.
Example: Practice
#include <iostream>
using namespace std;
int main() {
cout << "Compute each value/weight ratio by hand, sort by it, fill greedily to see why best-ratio-first wins";
return 0;
}public class Main {
public static void main(String[] args) {
System.out.println("Compute each value/weight ratio by hand, sort by it, fill greedily to see why best-ratio-first wins");
}
}print("Compute each value/weight ratio by hand, sort by it, fill greedily to see why best-ratio-first wins")#include <stdio.h>
int main() {
printf("Compute each value/weight ratio by hand, sort by it, fill greedily to see why best-ratio-first wins");
return 0;
}Login to try C/C++/Java code in the editor
Chapter Quiz — Complete all 5 topics to unlock
0/5 topics done
Complete these topics first: