31 lines
718 B
Python
31 lines
718 B
Python
def bisa_bayar(harga, pecahan):
|
|
# Menggunakan DP (subset sum)
|
|
dp = set()
|
|
dp.add(0)
|
|
|
|
for uang in pecahan:
|
|
baru = set(dp)
|
|
for nilai in dp:
|
|
total = nilai + uang
|
|
if total == harga:
|
|
return "YA"
|
|
if total < harga:
|
|
baru.add(total)
|
|
dp = baru
|
|
|
|
return "YA" if harga in dp else "TIDAK"
|
|
|
|
|
|
# Input beberapa baris (contoh seperti soal)
|
|
data = [
|
|
[4000, 200, 50, 25],
|
|
[2200, 1000],
|
|
[5500, 2000, 200, 100]
|
|
]
|
|
|
|
# Proses dan output
|
|
for i, baris in enumerate(data, start=1):
|
|
harga = baris[0]
|
|
pecahan = baris[1:]
|
|
hasil = bisa_bayar(harga, pecahan)
|
|
print(f"#{i}: {hasil}") |