Dynamic Programming Problems

Q1. Find the subset of numbers from a list which sum up to N.

Ans:

def longest_common_subsequence(M, nums):
    
    DP = [[False for _ in range(M+1)] for _ in range(len(nums)+1)]
    
    #Initialize the first row and colum to be True
    for i in range(len(nums)+1):
        DP[i][0] = True
    
    #Construct the rest of the table
 
    for i in range(1, len(nums)+1):
        for j in range(1, M+1):
                
            if j < nums[i-1]:   # if local sum value is less than the previous item
                DP[i][j] = DP[i-1][j]  # Don't include the item
                
            else:  # if local sum value is not less than the previous item
                if DP[i-1][j]:  # If previous cell value is True
                    DP[i][j] = DP[i-1][j]
                else:
                    DP[i][j] = DP[i-1][j-nums[i-1]]

    # Get the subset values which sum upto the desired sum.
    j = M
    i = len(nums)
    while i > 0 or j > 0:

        if DP[i][j] == DP[i-1][j]:  # If current cell item is same as above cell item. 
            i = i-1
        else:
            print('item for the subset: %d' % nums[i - 1])
            j = j-nums[i-1]  # Decrement the column index by actual integer, and decrement the row index by 1.
            i = i-1
        
                
M = 12
nums = [1, 2, 4, 6]

longest_common_subsequence(M, nums)