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

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

💡
Մետաղադրամների փոխարկման խնդիրը (Coin change) Դինամիկ Ծրագրավորման (Dynamic Programming) ամենահայտնի օրինակներից է. այն ցույց է տալիս, թե ինչպես Ագահ Ալգորիթմ (Greedy algorithm) կիրառելու դեպքում կարելի է ստանալ ոչ օպտիմալ պատասխան, իսկ Դինամիկ Ծրագրավորման միջոցով լիովին լուծել խնդիրը։
Տրված է դրամի համակարգ, որը կազմված է 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

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

  1. 11 → 1 + 5 + 5
  1. 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
  1. d = [0, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞]
  1. num = 1 ci = 1 ⇒ d[1] = d[0] + 1 = 1 ⇒ d = [0, 1, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞] ci = 5 ⇒ num - ci < 0 ci = 7 ⇒ num - ci < 0
  1. num = 2 ci = 1 ⇒ d[2] = d[1] + 1 = 2 ⇒ d = [0, 1, 2, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞] ci = 5 ⇒ num - ci < 0 ci = 7 ⇒ num - ci < 0
  1. 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
  1. 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
  1. 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
  1. 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
  1. 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, ∞, ∞, ∞, ∞]
  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 ⇒ չենք թարմացնում
  1. 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 ⇒ չենք թարմացնում
  1. 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 ⇒ չենք թարմացնում
  1. 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 ⇒ չենք թարմացնում
  1. print(d[11]) ⇒ տպում է 3
 
 

Constraints

Time limit: 5 seconds

Memory limit: 512 MB

Output limit: 1 MB

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