Մետաղադրամների փոխարկում (Coin change)

Տրված է դրամի համակարգ, որը կազմված է n մետաղադրամներից, որտեղ յուրաքանչյուր մետաղադրամի արժեքը դրական թիվ է։ Պահանջվում է ստանալ x գումարը հնարավորինս քիչ մետաղադրամների միջոցով:

Օրինակ, եթե մետաղադրամների արժեքներն են և անհրաժեշտ է ստանալ 11, լավագույն տարբերակը կլինի վերցնել 1 + 5 + 5 ⇒ 3 մետաղադրամ:

Մուտք

Մուտքի առաջին տողում տրված է երկու ամբողջ թիվ n (1 ≤ n ≤ 100) և x (1 ≤ x ≤ )։

Հաջորդ տողում գրված են n ամբողջ թվեր (1 ≤ ≤ )։

Ելք

Ծրագիրը պետք է արտահանի նվազագույն մետաղադրամների քանակը, որոնք անհրաժեշտ են x գումարը ստանալու համար։ Եթե հնարավոր չէ ստանալ x գումարը, պետք է տպել -1։

Օրինակներ

Մուտք	Ելք
3 11 1 5 7	3
3 12 1 5 7	2

Բացատրություն

11 → 1 + 5 + 5
12 → 5 + 7

Ուղեցույց

Հաշվի առեք, որ ամենամեծ հնարավոր մետաղադրամը մշտապես վերցնելը (ագահ մոտեցումը) օպտիմալ պատասխանի չի բերի։ Դա հստակ երևում է առաջին օրինակում։ Եթե վերցնենք 7-ը, ապա մնում է 4, որը կարող ենք ստանալ 4 հատ 1-ով. արդյունքում կօգտագործենք 5 մետաղադրամ, մինչդեռ իրական պատասխանը 3-ն է (5 + 5 + 1):

Եկեք սահմանենք d[i]-ն որպես նվազագույն մետաղադրամների քանակը, որոնք անհրաժեշտ են i գումարը ստանալու համար: Եթե կարողանանք ճիշտ սկզբնական արժեքներ տալ d զանգվածին, որից հետո ճիշտ լրացնել այն մինչև x-ը, ապա պատասխանը պարզապես կլինի d[x]:

d-ի բոլոր արժեքները սկզբում կարող ենք դնել անվերջություն՝ ∞ (որը ցույց կտա, որ տվյալ գումարը ստանալն հնարավոր չէ), բացի 0-ից, որը հնարավոր է ստանալ 0 մետաղադրամով.

c = [...]
x = ...
d = [0] + [float('inf')] * x      # d[0] = 0 և d[1...x] ներառյալ ∞

Այնուհետև, 1-ից մինչև x յուրաքանչյուր թվի համար պետք է փորձենք գտնել, թե ինչքան մետաղադրամ է հարկավոր այդ թիվը ստանալու համար: Եթե արդեն հասել ենք ինչ-որ num թվի, ապա ստուգում ենք բոլոր հնարավոր մետաղադրամները՝ արդյոք հնարավոր է ստանալ num արժեքը num - -ից +1 մետաղադրամով: Եթե դա փոքրացնում է պահանջվող մետաղադրամների թիվը, թարմացնում ենք d[num]-ը.

for num in range(1, x + 1):       # Անցնում ենք 1...x բոլոր թվերով
    for ci in c:                  # Փորձում ենք լավացնել d[num]-ի համար անհրաժեշտ մետաղադրամների թիվը
        if num - ci >= 0:         # Եթե կարելի է ստանալ num արժեքը ci մետաղադրամով
            d[num] = min(d[num], d[num - ci] + 1)
print(d[x])

d[num] = min(d[num], d[num - ci] + 1) տողը խնդրի լուծման առանցքային քայլն է. ամեն քայլին փորձում ենք լավացնել d[num]-ը ունենալով num - -ի համար ամենաօպտիմալ արժեքը, որին գումարում ենք 1՝ օգտագործելով մետաղադրամը:

Երբ բոլոր արժեքները հաշվել ենք, վերջնական պատասխանն ուղղակի d[x] արժեքն է:

Եկեք քայլ առ քայլ դիտարկենք ալգորիթմը տվյալ օրինակի վրա.

c = [1, 5, 7] և x = 11

d = [0, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞]
num = 1 ci = 1 ⇒ d[1] = d[0] + 1 = 1 ⇒ d = [0, 1, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞] ci = 5 ⇒ num - ci < 0 ci = 7 ⇒ num - ci < 0
num = 2 ci = 1 ⇒ d[2] = d[1] + 1 = 2 ⇒ d = [0, 1, 2, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞] ci = 5 ⇒ num - ci < 0 ci = 7 ⇒ num - ci < 0
num = 3 ci = 1 ⇒ d[3] = d[2] + 1 = 3 ⇒ d = [0, 1, 2, 3, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞] ci = 5 ⇒ num - ci < 0 ci = 7 ⇒ num - ci < 0
num = 4 ci = 1 ⇒ d[4] = d[3] + 1 = 4 ⇒ d = [0, 1, 2, 3, 4, ∞, ∞, ∞, ∞, ∞, ∞, ∞] ci = 5 ⇒ num - ci < 0 ci = 7 ⇒ num - ci < 0
num = 5 ci = 1 ⇒ d[5] = d[4] + 1 = 5 ⇒ d = [0, 1, 2, 3, 4, 5, ∞, ∞, ∞, ∞, ∞, ∞] ci = 5 ⇒ d[5] = d[0] + 1 = 1 ⇒ d = [0, 1, 2, 3, 4, 1, ∞, ∞, ∞, ∞, ∞, ∞] ci = 7 ⇒ num - ci < 0
num = 6 ci = 1 ⇒ d[6] = d[5] + 1 = 2 ⇒ d = [0, 1, 2, 3, 4, 1, 2, ∞, ∞, ∞, ∞, ∞] ci = 5 ⇒ չենք թարմացնում ci = 7 ⇒ num - ci < 0
num = 7 ci = 1 ⇒ d[7] = d[6] + 1 = 3 ⇒ d = [0, 1, 2, 3, 4, 1, 2, 3, ∞, ∞, ∞, ∞] ci = 5 ⇒ չենք թարմացնում ci = 7 ⇒ d[7] = d[0] + 1 = 1 ⇒ d = [0, 1, 2, 3, 4, 1, 2, 1, ∞, ∞, ∞, ∞]
num = 8 ci = 1 ⇒ d[8] = d[7] + 1 = 2 ⇒ d = [0, 1, 2, 3, 4, 1, 2, 1, 2, ∞, ∞, ∞] ci = 5 ⇒ չենք թարմացնում ci = 7 ⇒ չենք թարմացնում
num = 9 ci = 1 ⇒ d[9] = d[8] + 1 = 3 ⇒ d = [0, 1, 2, 3, 4, 1, 2, 1, 2, 3, ∞, ∞] ci = 5 ⇒ չենք թարմացնում ci = 7 ⇒ չենք թարմացնում
num = 10 ci = 1 ⇒ d[10] = d[9] + 1 = 4 ⇒ d = [0, 1, 2, 3, 4, 1, 2, 1, 2, 3, 4, ∞] ci = 5 ⇒ d[10] = d[5] + 1 = 2 ⇒ d = [0, 1, 2, 3, 4, 1, 2, 1, 2, 3, 2, ∞] ci = 7 ⇒ չենք թարմացնում
num = 11 ci = 1 ⇒ d[11] = d[10] + 1 = 3 ⇒ d = [0, 1, 2, 3, 4, 1, 2, 1, 2, 3, 2, 3] ci = 5 ⇒ չենք թարմացնում ci = 7 ⇒ չենք թարմացնում
print(d[11]) ⇒ տպում է 3

Constraints

Time limit: 5 seconds

Memory limit: 512 MB

Output limit: 1 MB