Experiment No.
Student Name: Preet UID: 24MCI10243
Branch: MCA Section/Group: 24MAM-4A
Semester: 1st Date of Performance: 30th Sep 2024
Subject Name: Design and analysis of algorithms Subject Code: 24CAP-612
Q. (1) Fractional Knapsack.
Aim/Overview of the practical:
The fractional knapsack problem aims to maximize the total value that can be placed in a
knapsack with a weight capacity limit, by allowing the addition of fraction items.
2. Task to be done
1) First we have to calculate the ratio(value/weight).
2) We have to sort the items in descending order according to their ratio.
3) Start taking the values into the knapsack as much as possible.
4) Continue filling the values until the knapsack is full, ensuring that the filled items are of the
highest value.
5) Stop when the knapsack is full or the items are finished.
3)Algorithms/flowchart:
1. You have n items, with weight and value.
2. Knapsack has a maximum capacity w.
3. Calculate the value-to-weight ratio.
4. Sort the items in descending order on their value-to-weight ratio.
5. Start adding items to the knapsack from the one with the highest value-to-weight ratio.
6. Else, add as much as possible to fill the knapsack to item capacity.
7. Repeat until the knapsack is full.
4. Dataset :
int val[] = {60, 100, 120};
int weight[] = {10, 20, 30};
int w = 50;
5. Code for experiment/practical:
import java. util.*;
class Item {
public static void main(String args[]) {
int val[] = {60, 100, 120}; int
weight[] = {10, 20, 30}; int w = 50;
double ratio [][] = new double[val.length][2];
for(int i = 0; i<val.length; i++) { ratio[i][0]
= i;
ratio[i][1] = val[i]/(double)weight[i];
Arrays.sort(ratio, Comparator.comparingDouble(o ->o[1]));
int cap = w; int finalval = 0;
for(int i = ratio.length-1; i>=0; i--) {
int idx = (int)ratio[i][0]; if(cap>=
weight[idx]) { finalval += val[idx];
cap -= weight[idx];
else{
finalval += (ratio[i][1] *cap);
cap = 0; break;
System.out.println("Total profit: "+finalval);
}
6. Result/Output/Writing Summary:
Learning outcomes (What I have learned):
1. Understand the concept of greedy algorithms.
2. Understand how to maximize the total value.
3. Understand that the problem can be solved while breaking into smaller subproblems.
4. Understand the importance of value-to-weight ratio in optimization problems.
