LCS knapsack code

Algorithms

Complete the following problem using python3 language. Please paste the codes using proper intended blocks with (Ctrl+shift+v). Also please provide the screenshots of the codes. Do not do mistake sir please follow the proper instructions. Thank you.i will up vote you if you do it unique and properly.do it in your own way.do not copy from others.thanks sir.

Note: please follow all the instruction given in the question.Read the question properly first.You have to read input from a fileTake input from files called "input1.txt", and output at "output1.txt"

Question:

Problem Description: The following tasks needed to be solved by using dynamic Programming. Dynamic programming is a way of finding the optimal solution of a problem where it reduces the call of functions by storing their results in every sequence. It compares the results of every step and from the comparison finds out the optimal solution. Longest common subsequence (LCS) is such an algorithm that functions as a dynamic approach. It basically finds out the longest subsequence which is common to the given sequences. Read the task descriptions carefully and implement the algorithm using Python .The output format MUST match exactly as shown in each task.

Note: please follow all the instruction given in the question.You have to read input from a file.Take input from files called "input1.txt", and output at "output1.txt", where X is the task number. Must be follow this.

Problem 1 (LCS) :

PUBGM (Player Unknowns BattleGrounds Mobile) is one of the most popular online battle royale games. PMPL (PUBGM Pro League) is the biggest tournament of south asia and Future Station a team from Bangladesh has qualified for the final round of the tournament. MagneT also known as The zone magnet for his accuracy of in-game zone predictions is the IGL (Team leader) of the team and he predicted the zone sequence before a match in the finals. For the match of map Erangel his prediction was,

On that match the team had a very good result and actual zone sequence of that match was:

Now, you have to find out the longest common zone sequence from MagneTs prediction and actual match by using LCS (Longest Common Subsequence) algorithm. Then verify the correctness of MagneTs prediction. For correctness you will use the formula given below. Correctness = (Length of longest common zone sequence 100) Number of zones Note: Zone meta given here is completely fictional. Please do not match it with the real game zone meta.

Hint: You have to store zone center values according to keywords first. You can use the following pseudo code of LCS algorithm.

LCS(X, Y): m = c[i,j-1]: c[i,j]

Sample Input: 8 //Number of zones YRSPFMHI //Zone sequence of the match YPSRFMHI //Zone sequence of MagneTs prediction

Sample Output: Yasnaya Pochinki Farm Mylta Shelter Prison Correctness of prediction: 75%

Zone number Zone center Keyword 1 Yasnaya Y 2 Pochinki P 3 School S 4 Rozhok R 5 Farm F 6 Mylta M EI 7 Shelter H 8 Prison | Zone number Zone center Keyword 1 Yasnaya Y 2. Rozhok R 3 School S 4 Pochinki P 5 Farm F 6 Mylta M 7 Shelter H 8 Prison |