paizaラーニング問題集「【部分和】部分和問題 4」を解いてみた

▼考え方

ポイントとなると思った考え方を、以下1.～4.に示します。

1.リストaの要素のうち、xを超える要素を排除したリストbを定義します。
a:[9,3,4,11,8]
b:[9,3,4,8]

2.リストbの各要素をxを超えない範囲で定数倍(1,2,...)し、リストcを定義します。
b:[9,3,4,8]
c:[9,3,6,9,4,8,8]

3.リストcを重複排除しリストeを定義します。
c:[9,3,6,9,4,8,8]
e:[9,3,6,4,8]

4.リストeに対し、部分和問題1の考え方と同様に処理を行います。

▼コード

########## 処理0(準備) インプット,リスト定義など ###########

n,x = map(int,input().split())

a = [0]*n
for i in range(n):
    a[i] = int(input())

# 考え方1.
b = [i for i in a if i <= x]

# 考え方2.
c = []
j = 1
for i in range(len(b)):
    while a[i]*j <= x:
        c.append(a[i]*j)
        j += 1
    j = 1

# 考え方3.
d = set(c)
e = list(d)

########## 処理1 漸化式の定義、計算、出力 ##########

# 考え方4.
dp = [0]*(x+1)
dp[0] = 1

for i in range(1,len(e)+1):

    for j in range(x,e[i-1]-1,-1):
        if dp[j-e[i-1]] == 1:
            dp[j] = 1
            
if dp[x] == 1:
    print("yes")
else:
    print("no")