paizaラーニング問題集「【全探索 2】コップの水」を解いてみた

▼考え方

この問題を解くために私が考えた内容1.～3.を以下に示します。

1.N個の小さなコップの組合せをすべて求め、それぞれの容量(ml)を計算します。その容量の中でX[ml]を超えないかつ最も大きい容量を出力します。

2.コップの組合せを求めるために、itertoolsというモジュールを使用します。以下に使用例を示します。

import itertools

w = [30,40,50]

print(list(itertools.combinations(w,1)))
# [(30,), (40,), (50,)] → 1個の小さなコップの組合せすべて

print(list(itertools.combinations(w,2)))
# [(30, 40), (30, 50), (40, 50)] → 2個の小さなコップの組合せすべて

print(list(itertools.combinations(w,3)))
# [(30, 40, 50)] → 3個の小さなコップの組合せすべて

3.小さなコップの組合せたときの水の合計量は、sum関数を使用して求めます。

▼コード

########## 処理0(準備) モジュールインポート,インプット ###########

# 考え方2.
import itertools

N,K = map(int,input().split())

w = [0]*N
for i in range(N):
    w[i] = int(input())

# max_ml: 大きなコップに入れられる水の最大量を格納する変数
max_ml = 0

# max_ml: 小さなコップの組合せたときの、水の合計量
tmp_ml = 0

########## 処理1 小さなコップの組合せたときの水の合計量のうち、大きなコップの容量を超えない最大値を求める ###########

for i in range(N):
    # 考え方2.
    wc = list(itertools.combinations(w,i+1))
    
    for j in range(len(wc)):
        # 考え方3.
        tmp_ml = sum(wc[j])
        
        if tmp_ml <= K and max_ml < tmp_ml:
            max_ml = tmp_ml

print(max_ml)