NORTH WESTERN UNIVERSITY,

KHULNA

Lab Raport

Course Code: CSE-2203

Submitted by Submitted to
Name: Swarnali Biswas Md Mahmuddul Hasan
ID: 20241013010 Lecturer
2ⁿᵈ Year 2ⁿᵈ semester
Section: A
Department of Computer Department of Computer
Science and Engineering. Science and Engineering.
North Western University, North Western University,
Khulna Khulna

Submission date
Lab Report: Fractional Knapsack using Greedy and
QuickSort

1. Introduction
The Fractional Knapsack Problem is a variation of the classical knapsack problem where
items can be broken into smaller pieces. The goal is to maximize total profit by selecting
items (or fractions of them) that fit into a knapsack of limited capacity. This problem is
efficiently solved using the Greedy Algorithm, by always choosing the item with the highest
profit-to-weight ratio first. To implement this, we sort items based on their ratio using
QuickSort.

2. Problem Formulation
Input:
- Number of items n.
- For each item: weight w[i], profit p[i].
- Knapsack capacity C.

Output:
- Maximum profit that can be obtained.
- (Optional) Items/fractions included in the knapsack.

Objective Function:
Maximize Σ (profit of items included), subject to Σ (weight) ≤ C.

3. Algorithm (Pseudo-code)
FractionalKnapsack(items[ ], n, C):
for each item i:
ratio[i] = profit[i] / weight[i]

QuickSort(items by ratio in descending order)

total_profit = 0
remaining_capacity = C

for i = 0 to n-1:
if items[i].weight <= remaining_capacity:
total_profit += items[i].profit
remaining_capacity -= items[i].weight
else:
total_profit += items[i].ratio * remaining_capacity
 remaining_capacity = 0;
break

return total_profit;

4. Implementation :

#include<iostream>

using namespace std;

struct items {

float weight;

float profit;

float wpp; // profit per weight

};

void insertionSort(items arr[], int n) {

for (int i = 1; i < n; i++) {

items key = arr[i];

int j = i - 1;

// Sort in descending order by wpp

while (j >= 0 && arr[j].wpp < [Link]) {

arr[j + 1] = arr[j];

j--;
 }

arr[j + 1] = key;

float fractionalknapsack(items item[], int n, float capacity) {

insertionSort(item, n);

float total_profit = 0.0;

float wt_taken = 0.0;

for (int i = 0; i < n; i++) {

if (wt_taken + item[i].weight <= capacity) {

total_profit += item[i].profit;

wt_taken += item[i].weight;

} else {

float remain = capacity - wt_taken;

total_profit += remain * item[i].wpp;

break; // knapsack full

return total_profit;

}
int main() {

int n;

float capacity;

cout << "Enter number of items: ";

cin >> n;

items item[n];

cout << "Enter weight and profit of each item:\n";

for (int i = 0; i < n; i++) {

cin >> item[i].weight >> item[i].profit;

item[i].wpp = item[i].profit / item[i].weight;

cout << "Enter knapsack capacity: ";

cin >> capacity;

float maxprofit = fractionalknapsack(item, n, capacity);

cout << "Max profit: " << maxprofit << endl;

return 0;

}
 5. Screenshot of Input/Output

6. Analysis
Time Complexity:
- QuickSort: O(n log n)
- Knapsack filling loop: O(n)
- Overall: O(n log n)

Space Complexity:
- Array of size n used for items.
- QuickSort recursion stack: O(log n)
- Overall: O(n)

1. Why different sorting techniques give different complexity?

Answers: Different sorting techniques give different time and space complexities because
of the way they approach the problem of arranging data. Each algorithm uses a distinct
logic, data movement strategy, and comparison method. For example:

Bubble Sort : Repeatedly compares adjacent elements and swaps them if needed. It has a
time complexity of O(n²) because every element is compared multiple times.
Merge Sort: Uses a divide-and-conquer strategy, breaking the array into halves and
merging them after sorting. It has O(n log n) complexity, which is much more efficient.

Quick Sort: Also uses divide-and-conquer but partitions around a pivot element. Its
average complexity is O(n log n), but in the worst case, it can be O(n²).

Heap Sort: builds a heap data structure and repeatedly extracts the maximum or minimum
element. It guarantees O(n log n) time complexity.

Hence, the difference in complexity arises due to their algorithmic design, the number of
comparisons and swaps, and the way they handle input data.

2. Why profit per weight is the best choice in fractional knapsack?

Answers: In the fractional knapsack problem, the goal is to maximize total profit without
exceeding the weight limit of the knapsack. Since we are allowed to take fractions of items,
the most efficient way to achieve this is by prioritizing items that provide the most profit
per unit weight.

This means calculating the ratio:

Profit per weight = Profit / Weight

By sorting items in descending order of this ratio and selecting from the top, we ensure that
every unit of weight added contributes the highest possible profit. This greedy approach
leads to the optimal solution for the fractional knapsack problem. Mathematically, this
works because the problem satisfies the greedy-choice property. A globally optimal
solution can be achieved by making locally optimal (greedy) choices at each step.