Open2

部分和問題やるとき、深さ探索やbit演算より動的計画やった方がスマートだったメモ

最初に思いつくのはdfs。

def dfs(i,sum):
	if i == len(s):
		return sum
	elif sum + s[i] > 2020:
		return dfs(i+1,sum)
	else:
		return max(dfs(i+1,sum),dfs(i+1,sum+s[i]))

次にbit演算。一番重い。

N = len(s)
ans = []
point = float('inf')
for i in range(1<<N):
    bit_matched = []
    for j in range(N):
        if (i>>j) & 1:
            bit_matched.append(s[j])
    current_point = abs(sum(bit_matched) - 2020)
    if current_point < point:
        point = current_point
        ans = bit_matched
import math
print(math.prod(ans), flush=True)

でもなーと思ってdpでやってみた。これが一番速い

dp = [-1 for i in range(2020+1)]
dp[0]=0
for i in s:
    for j in range(2020,-1,-1):
        if dp[j]==-1:
            continue;
        if j+i<=2020 and dp[j+i]==-1:
            dp[j+i]=i
    if dp[2020]!=-1:
        break;
result=[]
target=2020
while target!=0:
    result.append(dp[target])
    target = target-dp[target]
print(result, flush=True)

dpでやってるのは、和としてありえるdpを作成して、そこにあてこんでいく
2020に入ってるのが999だったら、2000-999=1001番目の配列にいく
1001に入ってるのが500だったら、1001-500-501番目の配列にいく
501=0だったら、そこで終わり。答えは999,500,501となる。dpに入ってなければskip、という感じで効率化できた。

ログインするとコメントできます