In [11]:

    

def findMaximum(a, k, n):
    maximum = [0 for i in range(k+1)]
    for i in range(1, k+1):
        for j in range(n):
            if a[j] <= i and maximum[i-a[j]] + a[j] > maximum[i]:
                maximum[i] = maximum[i-a[j]] + a[j]
    return maximum[k]


    

In [12]:

    

numberOfTestCases = 7
testCases = {1:[[3,9],[3,2,4]],2:[[3, 12],[3, 10, 4]],3:[[3,13],[3,10,4]],4:[[3,16],[3,10,4]],5:[[3,2000],[2000,2000,2000]],6:[[3,9],[9,9,9]],7:[[3,8],[9,9,9]]}
expected = {1:9,2:12,3:13,4:16,5:2000,6:9,7:0}

#for i in range(1, numberOfTestCases+1):
z = 3
for i in range(z, z+1):
    testCase = testCases[i]
    k = testCase[0][1]
    a = testCase[1]
    expectedResult = expected[i]
    #print("k=", k, " expected=", expectedResult, " a=", a, sep="")
    result = findMaximum(a, k, len(a))
    print(a, k, expectedResult, result, expectedResult == result)


    

    




[3, 10, 4] 13 13 13 True

In [ ]: