Fractional Knapsack समस्या

Fractional knapsack एक bag को sand या candy से भरने जैसा है जहां आप एक item का हिस्सा ले सकते हैं, पहले सबसे अच्छी value per weight लेते हुए।

In this page:

Problem Idea
Value per Weight
Take Full or Part
Greedy Strategy
Practice

Syntax

markup

items.sort(key=lambda x: x[0] / x[1], reverse=True)    # (value, weight)
total = 0
for value, weight in items:
    if capacity >= weight:
        capacity -= weight
        total += value
    else:
        total += value * capacity / weight
        break

Problem Idea

0-1 knapsack के विपरीत, fractional knapsack problem किसी item का कोई भी fraction लेने देती है — किसी 5 kg rice sack से बिल्कुल 2.5 kg निकाल पाने जैसा बजाय सिर्फ पूरी sack या कुछ नहीं लेने के।

उदाहरण: 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;
}

Value per Weight

Key ranking metric हर item के लिए value divided by weight है; इस ratio से items को highest से lowest तक sort करना आपको बताता है कौन से items उपयोग की गई capacity की प्रति unit सबसे ज़्यादा value देते हैं।

उदाहरण: 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;
}

Take Full or Part

Sorted list में नीचे काम करते हुए, current highest-ratio item का जितना fit हो उतना लें; एक बार कोई item बची capacity में पूरी तरह fit न हो, इसका बिल्कुल वह fraction लें जो fit हो और रुक जाएं, क्योंकि कोई higher-value-per-weight नहीं बचा।

उदाहरण: 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;
}

Greedy Strategy

यह greedy ratio-based strategy fractional version के लिए specifically provably optimal है क्योंकि partial items allowed हैं — उस तरह से बची capacity waste होने का कोई जोखिम नहीं जैसे 0-1 knapsack में all-or-nothing rule हो सकता है।

उदाहरण: 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;
}

Practice

हाथ से अलग-अलग weights और values वाले कुछ items से काम करें: हर ratio compute करें, इससे sort करें, और knapsack को greedily भरें यह देखने के लिए कि पहले best ratio लेना यहां दूसरे orderings को क्यों हमेशा हराता है।

उदाहरण: 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;
}

Chapter Quiz — Complete all 5 topics to unlock

0/5 topics done

Complete these topics first:

← Previous Lesson Activity Selection Problem Next Lesson → Huffman Coding