Assignment 4
Knapsack Algorithm:
Code:
#include <iostream>
#include <vector>
#include <algorithm>
class Item {
public:
double value;
double weight;
double ratio;
Item(double v, double w) : value(v), weight(w) {
ratio = value / weight;
};
// Comparator function to sort items by their value-to-weight ratio in descending order
bool compare(Item a, Item b) {
return a.ratio > b.ratio;
double fractional_knapsack(double capacity, std::vector<Item>& items) {
std::sort(items.begin(), items.end(), compare); // Sort items by ratio
double total_value = 0.0; // Total value accumulated
for (auto& item : items) {
if (capacity == 0) {
break;
}
// Determine the amount of the current item to take
double take_weight = std::min(item.weight, capacity);
total_value += take_weight * item.ratio;
capacity -= take_weight;
return total_value;
int main() {
int n;
std::cout << "Enter the number of items: ";
std::cin >> n;
std::vector<Item> items;
for (int i = 0; i < n; ++i) {
double value, weight;
std::cout << "Enter value and weight of item " << i + 1 << ": ";
std::cin >> value >> weight;
items.push_back(Item(value, weight));
double capacity;
std::cout << "Enter the capacity of the knapsack: ";
std::cin >> capacity;
double max_value = fractional_knapsack(capacity, items);
std::cout << "Maximum value in Knapsack = " << max_value << std::endl;
return 0;
}
Output:
Algorithm:
1. Start
2. Input the number of items n
3. Create a list items[] to store all items
4. For each item i from 1 to n:
Input the value value[i] and weight weight[i] of item i
Calculate the ratio of value to weight for the item:
o ratio[i] = value[i] / weight[i]
Add the item with its value, weight, and ratio to the items[] list
5. Input the capacity of the knapsack capacity
6. Sort the items[] in descending order based on ratio[i]
7. Initialize total_value = 0 to store the accumulated value
8. For each item i in the sorted items[]:
If capacity == 0, break the loop
Else:
o Calculate the weight to take from item i:
take_weight = min(weight[i], capacity)
o Add the value of the portion taken to total_value:
total_value += take_weight * ratio[i]
o Subtract the taken weight from capacity:
capacity -= take_weight
9. Output the total_value as the maximum value in the knapsack
10. End
Prims Algorithm:
Code:
#include <iostream>
#include <climits> // For INT_MAX
using namespace std;
// Function to find the vertex with minimum key value, from the set of vertices not yet included in MST
int findMinVertex(int key[], bool mstSet[], int n) {
int min = INT_MAX, minIndex;
for (int v = 0; v < n; v++) {
if (!mstSet[v] && key[v] < min) {
min = key[v];
minIndex = v;
return minIndex;
// Function to print the constructed Minimum Spanning Tree
void printMST(int parent[], int** graph, int n) {
cout << "Edge \tWeight\n";
for (int i = 1; i < n; i++)
cout << parent[i] << " - " << i << " \t" << graph[i][parent[i]] << " \n";
// Function to implement Prim's algorithm
void primMST(int** graph, int n) {
int parent[n]; // Array to store constructed MST
int key[n]; // Key values used to pick minimum weight edge in cut
bool mstSet[n]; // To represent set of vertices included in MST
// Initialize all keys as INFINITE and mstSet[] as false
for (int i = 0; i < n; i++) {
key[i] = INT_MAX;
mstSet[i] = false;
// Always include the first vertex in MST
key[0] = 0; // Make key 0 so that this vertex is picked as the first vertex
parent[0] = -1; // First node is always root of MST
// The MST will have n vertices
for (int count = 0; count < n - 1; count++) {
// Pick the minimum key vertex from the set of vertices not yet included in MST
int u = findMinVertex(key, mstSet, n);
// Add the picked vertex to the MST Set
mstSet[u] = true;
// Update key value and parent index of the adjacent vertices of the picked vertex
for (int v = 0; v < n; v++) {
// graph[u][v] is non-zero only for adjacent vertices of u
// mstSet[v] is false for vertices not yet included in MST
// Update the key only if graph[u][v] is smaller than key[v]
if (graph[u][v] && !mstSet[v] && graph[u][v] < key[v]) {
parent[v] = u;
key[v] = graph[u][v];
// Print the constructed MST
printMST(parent, graph, n);
int main() {
int n;
cout << "Enter the number of vertices: ";
cin >> n;
// Dynamically allocate memory for the adjacency matrix
int** graph = new int*[n];
for (int i = 0; i < n; i++) {
graph[i] = new int[n];
cout << "Enter the adjacency matrix (enter 0 for no edge): \n";
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> graph[i][j];
primMST(graph, n);
// Deallocate the memory for the graph
for (int i = 0; i < n; i++) {
delete[] graph[i];
delete[] graph;
return 0;
Output:
Algorithm:
