मान लीजिए कि हमारे पास दो अंकीय तार ए और बी हैं। हमें ए और बी को समान बनाने के लिए न्यूनतम लागत का पता लगाना है। हम केवल एक ही ऑपरेशन कर सकते हैं, यानी हम स्ट्रिंग से अंकों को हटा सकते हैं, संख्या से एक अंक को हटाने की लागत अंकों के मूल्य के समान है। मान लीजिए कि स्ट्रिंग A ="6789", B ="7859", तो हमें A से 6 हटाना है, और B से 5 हटाना है, इसलिए लागत 5 + 6 =11 होगी।
यह सबसे लंबी सामान्य बाद की समस्या की भिन्नता में से एक है। हमें A और B से LCS की लंबाई ज्ञात करनी है, इस सूत्र का उपयोग करके हम न्यूनतम लागत प्राप्त कर सकते हैं।
न्यूनतम लागत=कॉस्टए+कॉस्टबी-2∗lcs<उप>लागत
उदाहरण
#include <iostream>
using namespace std;
int longest_common_subsequence(int dp[101][101], string a, string b, int a_len,
int b_len) {
for (int i = 0; i < 100; i++)
for (int j = 0; j < 100; j++)
dp[i][j] = -1;
if (a_len < 0 || b_len < 0) {
return 0;
}
if (dp[a_len][b_len] != -1)
return dp[a_len][b_len];
int res = 0;
if (a[a_len] == b[b_len]) {
res = int(a[a_len] - 48) + longest_common_subsequence(dp, a, b, a_len - 1, b_len - 1);
} else
res = max(longest_common_subsequence(dp, a, b, a_len - 1, b_len),
longest_common_subsequence(dp, a, b, a_len, b_len - 1));
dp[a_len][b_len] = res;
return res;
}
int minCost(string str) {
int cost = 0;
for (int i = 0; i < str.length(); i++)
cost += int(str[i] - 48);
return cost;
}
int main() {
string a, b;
a = "6789";
b = "7859";
int dp[101][101];
cout << "Minimum Cost to make these two numbers identical: " << (minCost(a) + minCost(b) - 2 * longest_common_subsequence(dp, a, b, a.length() - 1, b.length() - 1));
return 0;
} आउटपुट
Minimum Cost to make these two numbers identical: 11