Scribd
Upload
2 views5 pages

C++ Dynamic Programming Algorithms

The document contains C++ implementations of various algorithms including the 01 Knapsack problem, Longest Common Subsequence (LCS), Matrix Chain Multiplication (MCM), Resource Allocation Problem, and the Floyd-Warshall algorithm for finding all pair shortest paths. Each algorithm is presented with its respective function and logic for solving the problem efficiently using dynamic programming techniques. The code snippets provide a clear structure for understanding the implementation of these algorithms.

Uploaded by

dishantmarchant12345
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
2 views5 pages

C++ Dynamic Programming Algorithms

The document contains C++ implementations of various algorithms including the 01 Knapsack problem, Longest Common Subsequence (LCS), Matrix Chain Multiplication (MCM), Resource Allocation Problem, and the Floyd-Warshall algorithm for finding all pair shortest paths. Each algorithm is presented with its respective function and logic for solving the problem efficiently using dynamic programming techniques. The code snippets provide a clear structure for understanding the implementation of these algorithms.

Uploaded by

dishantmarchant12345
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

01 Knapsack (C++)

int knapSack(int W, vector<int>& wt, vector<int>& val, int n) {


vector<vector<int>> dp(n+1, vector<int>(W+1, 0));

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


for(int w = 1; w <= W; w++){
if(wt[i-1] <= w)
dp[i][w] = max(val[i-1] + dp[i-1][w-wt[i-1]],
dp[i-1][w]);
else
dp[i][w] = dp[i-1][w];
}
}
return dp[n][W];
}
LCS (Longest Common Subsequence - C++)
int lcs(string X, string Y) {
int n = [Link](), m = [Link]();
vector<vector<int>> dp(n+1, vector<int>(m+1, 0));

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


for(int j = 1; j <= m; j++){
if(X[i-1] == Y[j-1])
dp[i][j] = 1 + dp[i-1][j-1];
else
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
return dp[n][m];
}
Matrix Chain Multiplication (MCM - C++)
int matrixChainOrder(vector<int>& dims) {
int n = [Link]();
vector<vector<int>> dp(n, vector<int>(n, 0));

for(int len = 2; len < n; len++){


for(int i = 1; i < n - len + 1; i++){
int j = i + len - 1;
dp[i][j] = INT_MAX;

for(int k = i; k < j; k++){


int cost = dp[i][k] + dp[k+1][j] + dims[i-1]*dims[k]*dims[j];
dp[i][j] = min(dp[i][j], cost);
}
}
}
return dp[1][n-1];
}
Resource Allocation Problem (Max Profit - C++)
int resourceAllocation(vector<int>& cost, vector<int>& profit, int budget) {
int n = [Link]();
vector<int> dp(budget+1, 0);

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


for(int b = budget; b >= cost[i]; b--){
dp[b] = max(dp[b], profit[i] + dp[b - cost[i]]);
}
}
return dp[budget];
}
All Pair Shortest Paths (Floyd-Warshall - C++)
void floydWarshall(vector<vector<int>>& dist) {
int n = [Link]();

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


for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(dist[i][k] != INT_MAX && dist[k][j] != INT_MAX)
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
}

You might also like