C Program for 0-1 Knapsack Problem Using Memoization

// C Program for 0-1 KnapSack Problem using Recursion + Memoization

#include <stdio.h>

// Maximum number of items and maximum capacity of the

// knapsack

#define MAX_ITEMS 100

#define MAX_CAPACITY 100

// Memoization table

int dp[MAX_ITEMS][MAX_CAPACITY];

// Function that returns maximum of two integers

int max(int a, int b)

if (a > b)

return a;

return b;

// Recursive function with memoization

int knapSackMemo(int W, int wt[], int val[], int n)

// Base Case

if (n == 0 || W == 0)

return 0;

// If value is already calculated, return it

if (dp[n][W] != -1)

return dp[n][W];
 if (wt[n - 1] > W)

return dp[n][W] = knapSackMemo(W, wt, val, n - 1);

else

return dp[n][W]

= max(val[n - 1]

+ knapSackMemo(W - wt[n - 1], wt,

val, n - 1),

knapSackMemo(W, wt, val, n - 1));

int main()

int values[] = { 3, 4, 5, 6 };

int weight[] = { 2, 3, 4, 5 };

int W = 8;

int n = sizeof(values) / sizeof(values[0]);

// Initialize dp array with -1 (indicating that the

// subproblem is not yet solved)

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

for (int j = 0; j <= W; ++j) {

dp[i][j] = -1;

// Output the maximum profit of the knapSack

printf(

"Maximum value that can be put in knapsack: %d\n",

knapSackMemo(W, weight, values, n));

// C Program for Travelling Salesman using Dynamic Programming

#include <stdio.h>

#include <limits.h>

#define MAX 9999

int n = 4;

int distan[20][20] = {

{0, 22, 26, 30},

{30, 0, 45, 35},

{25, 45, 0, 60},

{30, 35, 40, 0}};

int DP[32][8];

int TSP(int mark, int position) {

int completed_visit = (1 << n) - 1;

if (mark == completed_visit) {

return distan[position][0];

if (DP[mark][position] != -1) {

return DP[mark][position];

int answer = MAX;

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

if ((mark & (1 << city)) == 0) {

int newAnswer = distan[position][city] + TSP(mark | (1 << city), city);

answer = (answer < newAnswer) ? answer : newAnswer;

}
 }

return DP[mark][position] = answer;

int main() {

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

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

DP[i][j] = -1;

printf("Minimum Distance Travelled -> %d\n", TSP(1, 0));

return 0;

// A C program for Prim's Minimum

// Spanning Tree (MST) algorithm. The program is

// for adjacency matrix representation of the graph

#include <limits.h>

#include <stdbool.h>

#include <stdio.h>

// Number of vertices in the graph

#define V 5

// A utility function to find the vertex with

// minimum key value, from the set of vertices

// not yet included in MST

int minKey(int key[], bool mstSet[])

// Initialize min value

for (int v = 0; v < V; v++)

if (mstSet[v] == false && key[v] < min)

min = key[v], min_index = v;

return min_index;

// A utility function to print the

// constructed MST stored in parent[]

int printMST(int parent[], int graph[V][V])

printf("Edge \tWeight\n");

for (int i = 1; i < V; i++)

printf("%d - %d \t%d \n", parent[i], i,

graph[parent[i]][i]);

// Function to construct and print MST for

// a graph represented using adjacency

// matrix representation

void primMST(int graph[V][V])

// Array to store constructed MST

int parent[V];

// Key values used to pick minimum weight edge in cut

int key[V];

// To represent set of vertices included in MST

bool mstSet[V];
// Initialize all keys as INFINITE

for (int i = 0; i < V; i++)

key[i] = INT_MAX, mstSet[i] = false;

// Always include first 1st vertex in MST.

// Make key 0 so that this vertex is picked as first

// vertex.

key[0] = 0;

// First node is always root of MST

parent[0] = -1;

// The MST will have V vertices

for (int count = 0; count < V - 1; count++) {

// Pick the minimum key vertex from the

// set of vertices not yet included in MST

int u = minKey(key, mstSet);

// 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.

// Consider only those vertices which are not

// yet included in MST

for (int v = 0; v < V; v++)

// graph[u][v] is non zero only for adjacent

// vertices of m mstSet[v] is false for vertices

// not yet included in MST Update the key only

if (graph[u][v] && mstSet[v] == false

&& graph[u][v] < key[v])

parent[v] = u, key[v] = graph[u][v];

// print the constructed MST

printMST(parent, graph);

// Driver's code

int main()

int graph[V][V] = { { 0, 2, 0, 6, 0 },

{ 2, 0, 3, 8, 5 },

{ 0, 3, 0, 0, 7 },

{ 6, 8, 0, 0, 9 },

{ 0, 5, 7, 9, 0 } };

// Print the solution

primMST(graph);

return 0;

}
// C code to implement Kruskal's algorithm

#include <stdio.h>

#include <stdlib.h>

// Comparator function to use in sorting

int comparator(const int p1[], const int p2[])

return p1[2] - p2[2];

// Initialization of parent[] and rank[] arrays

void makeSet(int parent[], int rank[], int n)

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

parent[i] = i;

rank[i] = 0;

// Function to find the parent of a node

int findParent(int parent[], int component)

if (parent[component] == component)

return component;

return parent[component]

= findParent(parent, parent[component]);

// Function to unite two sets

// Finding the parents

u = findParent(parent, u);

v = findParent(parent, v);

if (rank[u] < rank[v]) {

parent[u] = v;

else if (rank[u] > rank[v]) {

parent[v] = u;

else {

parent[v] = u;

// Since the rank increases if

// the ranks of two sets are same

rank[u]++;

// Function to find the MST

int kruskalAlgo(int n, int edge[n][3])

// First we sort the edge array in ascending order

// so that we can access minimum distances/cost

qsort(edge, n, sizeof(edge[0]), comparator);

int parent[n];

int rank[n];
 // Function to initialize parent[] and rank[]

makeSet(parent, rank, n);

// To store the minimun cost

int minCost = 0;

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

int v1 = findParent(parent, edge[i][0]);

int v2 = findParent(parent, edge[i][1]);

int wt = edge[i][2];

// If the parents are different that

// means they are in different sets so

// union them

if (v1 != v2) {

unionSet(v1, v2, parent, rank, n);

minCost += wt;

return minCost;

// Driver code

int main()

int edge[5][3] = { { 0, 1, 10 },

{ 0, 2, 6 },

{ 0, 3, 5 },

{ 1, 3, 15 },

{ 2, 3, 4 } };
 printf("%d",kruskalAlgo(5, edge));

return 0;