PBT | July 7 | Coding

Problem 1:

Given two sequences, find the length of longest subsequence present in both of them. Both the strings

are of uppercase.

Input Format

First line of input contains 'n', size of first string. Second line of input contains 'm', size of second string.

Third line of input contains string s1. Fourth line of input contains string s2.

Constraints

1<=size(str1),size(str2)<=103

Output Format

Print the length of longest subsequence present in both of them

Python Code:

 def lcs(X, Y, m, n):
 
    if m == 0 or n == 0:
       return 0;
    elif X[m-1] == Y[n-1]:
       return 1 + lcs(X, Y, m-1, n-1);
    else:
       return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n));
n1=int(input())
n2=int(input())
X = input()
Y = input()
print (lcs(X , Y, len(X), len(Y)))

Problem 2:

You are given weights and values of N items, put these items in a knapsack of capacity W to get the

maximum total value in the knapsack. Note that we have only one quantity of each item.

In other words, given two integer arrays val0..N-1 and wt0..N-1 which represent values and weights

associated with N items respectively. Also given an integer W which represents knapsack capacity, find

out the maximum value subset of val[] such that sum of the weights of this subset is smaller than or

equal to W. You cannot break an item, either pick the complete item, or don’t pick it (0-1 property).

Input Format

First line of input contains N.

Second line of input contains W.

Third line of input contains N integers, elements of val array.

Fourth line of input contains N integers elements of wt array,

Constraints

1 ≤ N ≤ 1000

1 ≤ W ≤ 1000

1 ≤ wti ≤ 1000

1 ≤ vi ≤ 1000

Output Format

Print the maximum value subset of val[] such that sum of the weights of this subset is smaller than or

equal to W.

Python Code:

def knapSack(W, wt, val, n):
    if n == 0 or W == 0:
        return 0
    if (wt[n-1] > W):
        return knapSack(W, wt, val, n-1)
    else:
        return max(
            val[n-1] + knapSack(
                W-wt[n-1], wt, val, n-1),
            knapSack(W, wt, val, n-1))

n=int(input())
W=int(input())
val = list(map(int,input().split()))
wt = list(map(int,input().split()))
print(knapSack(W, wt, val, n))