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

Մետաղադրամների փոխարկում (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 - ci արժեքը հասանելի է ամենաքիչ մետաղադրամով, որին գումարում ենք 1 (մեր օգտագործվող ci մետաղադրամը):
Երբ բոլոր արժեքները հաշվել ենք, վերջնական պատասխանն ուղղակի 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 ⇒ does not update 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 ⇒ does not update 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 ⇒ does not update ci = 7 ⇒ does not update
  1. num = 9 ci = 1 ⇒ d[9] = d[8] + 1 = 3 ⇒ d = [0, 1, 2, 3, 4, 1, 2, 1, 2, 3, ∞, ∞] ci = 5 ⇒ does not update ci = 7 ⇒ does not update
  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 ⇒ does not update
  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 ⇒ does not update ci = 7 ⇒ does not update
  1. print(d[11]) ⇒ տպում է 3
 

Constraints

Time limit: 2.5 seconds

Memory limit: 512 MB

Output limit: 1 MB

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