मान लीजिए कि हमारे पास पांच संख्याएं हैं, एन, ए, बी, सी, डी। हम संख्या 0 से शुरू करते हैं और एन पर समाप्त होते हैं। हम निम्नलिखित परिचालनों के साथ निश्चित संख्या में सिक्कों द्वारा एक संख्या बदल सकते हैं -
- एक सिक्के का भुगतान करके, संख्या को 2 से गुणा करें
- बी सिक्कों का भुगतान करके संख्या को 3 से गुणा करें
- सी सिक्कों का भुगतान करते हुए संख्या को 5 से गुणा करें
- डी सिक्कों का भुगतान करके संख्या को 1 से बढ़ाएं या घटाएं।
हम इन कार्यों को किसी भी क्रम में कितनी भी बार कर सकते हैं। हमें N तक पहुँचने के लिए आवश्यक न्यूनतम सिक्कों की संख्या ज्ञात करनी होगी
तो, अगर इनपुट एन =11 की तरह है; ए =1; बी =2; सी =2; D =8, तो आउटपुट 19 होगा, क्योंकि प्रारंभ में x 0 है।
8 सिक्कों के लिए x को 1 (x=1) से बढ़ाने के लिए।
1 सिक्के के लिए, x को 2 (x=2) से गुणा करें।
2 सिक्कों के लिए, x को 5 (x=10) से गुणा करें।
8 सिक्कों के लिए, इसे 1 (x=11) बढ़ाएं।
कदम
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
Define one map f for integer type key and value Define one map vis for integer type key and Boolean type value Define a function calc, this will take n if n is zero, then: return 0 if n is in vis, then: return f[n] vis[n] := 1 res := calc(n / 2) + n mod 2 * d + a if n mod 2 is non-zero, then: res := minimum of res and calc((n / 2 + 1) + (2 - n mod 2)) * d + a) res := minimum of res and calc(n / 3) + n mod 3 * d + b if n mod 3 is non-zero, then: res := minimum of res and calc((n / 3 + 1) + (3 - n mod 3)) * d + b) res := minimum of res and calc(n / 5) + n mod 5 * d + c if n mod 5 is non-zero, then: res := minimum of res and calc((n / 5 + 1) + (5 - n mod 5)) if (res - 1) / n + 1 > d, then: res := n * d return f[n] = res From the main method, set a, b, c and d, and call calc(n)
उदाहरण
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
#include <bits/stdc++.h>
using namespace std;
int a, b, c, d;
map<long, long> f;
map<long, bool> vis;
long calc(long n){
if (!n)
return 0;
if (vis.find(n) != vis.end())
return f[n];
vis[n] = 1;
long res = calc(n / 2) + n % 2 * d + a;
if (n % 2)
res = min(res, calc(n / 2 + 1) + (2 - n % 2) * d + a);
res = min(res, calc(n / 3) + n % 3 * d + b);
if (n % 3)
res = min(res, calc(n / 3 + 1) + (3 - n % 3) * d + b);
res = min(res, calc(n / 5) + n % 5 * d + c);
if (n % 5)
res = min(res, calc(n / 5 + 1) + (5 - n % 5) * d + c);
if ((res - 1) / n + 1 > d)
res = n * d;
return f[n] = res;
}
int solve(int N, int A, int B, int C, int D){
a = A;
b = B;
c = C;
d = D;
return calc(N);
}
int main(){
int N = 11;
int A = 1;
int B = 2;
int C = 2;
int D = 8;
cout << solve(N, A, B, C, D) << endl;
} इनपुट
11, 1, 2, 2, 8
आउटपुट
19