Ալգորիթմներ և Տվյալների Կառուցվածքներ

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

Ենթադրենք ունենք դրամային համակարգ, որը բաղկացած է n մետաղադրամից, և յուրաքանչյուր մետաղադրամի արժեքը դրական թիվ է։ Ձեզ խնդրում են պարզել, թե քանի տարբեր եղանակով է կարելի ստանալ x գումարը, օգտագործելով այդ մետաղադրամները։
Օրինակ, եթե մետաղադրամների արժեքներն են և անհրաժեշտ է ստանալ 5 գումարը, ապա կարելի է դա անել 4 տարբեր ձևերով. 5, 1 + 2 + 2, 1 + 1 + 1 + 2 և 1 + 1 + 1 + 1 + 1։ Ի տարբերություն combination sum խնդիրների, այստեղ հերթականությունը նշանակություն չունի, այսինքն՝ մեզ հետաքրքրում է միայն մետաղադրամների բազմությունը, այլ ոչ թե դրանց դրված կարգը։

Մուտք

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

Ելք

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

Օրինակներ

Մուտք
Ելք
3 5 1 2 5
4
3 9 2 3 5
3

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

  1. 5, 1 + 2 + 2, 1 + 1 + 1 + 2 և 1 + 1 + 1 + 1 + 1
  1. 3 + 3 + 3, 2 + 2 + 5, 2 + 2 + 2 + 3
 

Ուղեցույց

Ուշադրություն դարձրեք, որ եթե օգտագործենք միայն d[s] տեսքով վիճակ, որտեղ d[s]-ը ցույց է տալիս, թե քանի եղանակով կարելի է ստանալ s գումարը մետաղադրամների միջոցով, մեզ մոտ կառաջանա կրկնահաշվարկի խնդիր։ Օրինակ, 1 + 2 + 2 բազմությունը, որը պետք է հաշվել միայն մեկ անգամ, կգրանցվեր 3 անգամ (տարբեր հերթականություններով)։
Այս խնդիրը լուծելու համար մենք կհաշվենք s գումարը ստանալու տարբեր ձևերի քանակը՝ մինչև ci ինդեքսով մետաղադրամներն օգտագործելով (այստեղ ci-ն c արժեքով մետաղադրամի ինդեքսն է)։ Կարող ենք նաև չօգտագործել ci մետաղադրամը, կամ օգտագործել այն մի քանի անգամ. այդ տարբերակները կարտացոլվեն մեր վիճակում։ Այսպիսով, d[s][ci]-ն ցույց է տալիս, թե քանի ձևով կարելի է ստանալ s գումարը, եթե հաշվի ենք առնում բոլոր մետաղադրամները մինչև ci-ն ներառյալ։
 
Կա 2 վիճակի անցում, որոնց միջոցով կարելի է ստանալ d[s][ci] վիճակը (երբ ներկա մետաղադրամի ինդեքսը ci է, իսկ արժեքը val).
  1. Չօգտագործել ci մետաղադրամը → d[s][ci - 1]
  1. Օգտագործել ci մետաղադրամը 0, 1, 2, … k անգամ → d[s - val][ci]
Ըստ այդմ, s գումարը ստանալու տարբերակների ընդհանուր թիվը կլինի վերոնշյալ երկու անցումներից գոյացող արժեքների գումարը։
 
c = [...]
x = ...
# d-ն նախապես լցնում ենք (x+1) տողանոց և len(c) սյունանոց 0-ներով
d = [[0] * len(c) for _ in range(x + 1)]
Նախ մշակում ենք առաջին մետաղադրամը և ընտրում, թե ինչպես կարելի է ստանալ տարբեր գումարներ դրանից օգտվելով: Հետո անցնում ենք երկրորդ մետաղադրամին և թարմացնում d[s][1] վիճակները, այնուհետև երրորդին և այդպես շարունակ, մինչև մշակում ենք բոլոր մետաղադրամները։
Վերջում, երբ բոլոր մետաղադրամները հաշվի են առնված, տպում ենք, թե քանի եղանակով է կարելի հասնել x գումարին. այն կլինի d[x][len(c) - 1]-ի արժեքը.
for ci, val in enumerate(c):      # Հերթով անցնում ենք մետաղադրամների վրայով
    d[0][ci] = 1                  # Հնարավոր է ստանալ 0 գումար առանց որևէ մետաղադրամի
    for s in range(1, x + 1):     # Փորձում ենք բոլոր գումարները 1...x միջակայքում
        if ci - 1 >= 0:           # (1) չօգտագործել ci մետաղադրամը
            d[s][ci] += d[s][ci - 1]
        if s - val >= 0:          # (2) օգտագործել ci-ն 0-ից ավել անգամներ
            d[s][ci] += d[s - val][ci]

print(d[x][len(c) - 1])
 
😎 Կարո՞ղ եք մտածել մի միջոց, որպեսզի d-ն միաչափ ցուցակ լինի:
Մենք մետաղադրամները մշակում ենք հերթով, հետևաբար կարող ենք «հեռացնել» նախորդ մետաղադրամներից ստացված միջանկյալ արդյունքները, որոնք այլևս հարկավոր չեն։ Յուրաքանչյուր փուլում մեզ անհրաժեշտ են միայն ընթացիկ ci և նախորդ ci - 1 մետաղադրամի արժեքները։ Ուրեմն, կարելի է պահել նախորդ մետաղադրամի վիճակները մեկ զանգվածում, իսկ ընթացիկի վիճակները՝ մյուսում։
😎 Կարո՞ղ եք այնպես անել, որ կողմնակի զանգված ընդհանրապես չօգտագործվի և միայն միաչափ d-ն պահվի:
Կարելի է նկատել, որ նախորդ մետաղադրամի վիճակներից պահանջվում է միայն գումարել prev[s]-ը d[s]-ին։ Դրա շնորհիվ կարելի է շրջանցել նախորդ զանգվածի պահպանումը.
# Նախապես d-ում դնել 1 (s=0) և մնացածը 0
d = [1] + [0] * x                 # 0 գումարը կարելի է ստանալ առանց մետաղադրամների

for ci, val in enumerate(c):      # Հերթով անցնում ենք մետաղադրամների վրայով
    for s in range(1, x + 1):     # Փորձում ենք 1...x գումարները
        if s - val >= 0:          # (2) օգտագործել ci-ն 0-ից ավել անգամներ
            d[s] += d[s - val]
        d[s] %= MOD

print(d[x])
 

Constraints

Time limit: 4 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue