Блог

Я решаю вопрос о CodeChef, который в основном является проблемой суммы подмножеств. Когда бандит подходит к вам в темном переулке, он просит у вас определенную сумму денег. Вы обязаны показать ему все деньги, которые у вас есть, но вам нужно заплатить, только если он сможет найти подмножество ваших банкнот, общая стоимость которых соответствует его требованию. Поскольку банкноты в Byteland могут иметь любое положительное целое значение меньше тысячи, вы, скорее всего, останетесь без оплаты.

Ввод:

Первая строка содержит целое число t, количество тестовых примеров (около 100). Затем следуют t тестовых примеров. Каждый тестовый пример начинается с n, количества банкнот в вашем кошельке, и m, суммы денег, которую у вас попросили грабители. Затем следует n чисел, представляющих значения ваших банкнот. В вашем кошельке не более 20 банкнот, а стоимость одной банкноты никогда не превышает 1000.

Вывод:

Для каждого тестового примера выведите одну строку со словом «Да», если есть подмножество ваших банкнот, сумма которых равна m, и «Нет» в противном случае.

Пример

Ввод:

 5
3 3
1
1
1
5 11
1
2
4
8
16
5 23
1
2
4
8
16
5 13
1
5
5
10
10
  

Вывод:

 Yes
Yes
Yes
No
  

Мой код:

 for _ in range(int(input())):
    n,sum1 = map(int,input().split())
    arr = []
    for i in range(n):
        arr.append(int(input()))
    matrix = [[False for i in range(sum1 1)] for j in range(n 1)]
    for i in range(n 1):
        for j in range(sum1 1):
            if i==0:
                matrix[i][j] = False
            if j==0:
                matrix[i][j] = True
            if arr[i-1]<=j:
                matrix[i][j] = matrix[i-1][j-arr[i-1]] or matrix[i-1][j]
            elif arr[i-1]>j:
                matrix[i][j] = matrix[i-1][j]
    if matrix[n][sum1]==True:
        print("Yes")
    else:
        print("No")
  

Почему я получаю неправильный ответ?

Редактировать: это правильное решение проблемы с суммой подмножеств

 n = len(A)

    # T[i][j] stores true if subset with sum j can be attained with
    # using items up to first i items
    T = [[False for x in range(sum   1)] for y in range(n   1)]

    # if sum is zero
    for i in range(n   1):
        T[i][0] = True

    # do for ith item
    for i in range(1, n   1):
        # consider all sum from 1 to sum
        for j in range(1, sum   1):
            # don't include ith element if j-A[i-1] is negative
            if A[i - 1] > j:
                T[i][j] = T[i - 1][j]
            else:
                # find subset with sum j by excluding or including the i'th item
                T[i][j] = T[i - 1][j] or T[i - 1][j - A[i - 1]]

    # return maximum value
    return T[n][sum]


if __name__ == '__main__':

    # Input: set of items and a sum
    A = [7, 3, 2, 5, 8]
    sum = 18

    if subsetSum(A, sum):
        print("Yes")
    else:
        print("No")
  

Если я инициализировал свой список DP из приведенного выше подхода, это дает мне правильный вывод. Но я не могу понять, в чем проблема в моей логике инициализации списка DP ( t в моем коде).