[go: up one dir, main page]
Scribd
Upload
10 views3 pages

Knapsack & LCS

Uploaded by

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

Knapsack & LCS

Uploaded by

Jak Khan
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 3

Knapsack

#include <iostream>
using namespace std;

int knapsack(int Capacity, int weights[], int values[], int item)


{
int dp[item + 1][Capacity + 1];
for (int i = 0; i <= item; i++)
{
for (int w = 0; w <= Capacity; w++)
{
if (i == 0 || w == 0)
dp[i][w] = 0;
else if (weights[i - 1] <= w)
dp[i][w] = max(values[i - 1] + dp[i - 1][w - weights[i -
1]], dp[i - 1][w]);
else
dp[i][w] = dp[i - 1][w];
}
}
return dp[item][Capacity];
}

int main()
{
int item, Capacity;
cout << "Number of items: ";
cin >> item;
cout << "Knapsack capacity: ";
cin >> Capacity;

int weights[item], values[item];


cout << "Enter weight and value: " << endl;
for (int i = 0; i < item; i++)
{
cin >> weights[i] >> values[i];
}
cout << "Max Profit: " << knapsack(Capacity, weights, values, item)
<< endl;
return 0;
}
LCS
#include <iostream>
#include <cstring>
using namespace std;

int lcs(char *A, char *B, int m, int n)


{
int dp[100][100]; // Adjust size as needed
for (int i = 0; i <= m; i++)
{
for (int j = 0; j <= n; j++)
{
if (i == 0 || j == 0)
dp[i][j] = 0;
else if (A[i - 1] == B[j - 1])
dp[i][j] = dp[i - 1][j - 1] + 1;
else
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
return dp[m][n];
}

int main()
{
char A[100], B[100];
cin >> A >> B;
int m = strlen(A), n = strlen(B);
cout << "LCS: " << lcs(A, B, m, n);
return 0;
}

You might also like