मान लीजिए हमारे पास धनात्मक संख्याओं की एक सरणी है; हम उस सरणी के प्रत्येक तत्व को प्रतिस्थापित करते हैं ताकि सरणी में दो आसन्न तत्वों के बीच का अंतर या तो दिए गए लक्ष्य से कम हो या उसके बराबर हो। अब, हमें समायोजन लागत को न्यूनतम करना है, इसलिए नए मूल्य और पुराने मूल्य के बीच अंतर का योग। अधिक सटीक रूप से, हम Σ|A[i] – Anew[i]| को न्यूनतम करते हैं जहां i की सीमा 0 से n-1 तक है, यहां n को A के आकार के रूप में दर्शाया गया है और Anew वह सरणी है जिसमें आसन्न अंतर लक्ष्य से कम या बराबर है।
तो, यदि इनपुट [56, 78, 53, 62, 40, 7, 26, 61, 50, 48], target = 20 की तरह है, तो आउटपुट 25 होगा।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
n := arr का आकार
table := [[0 for i in range 0 to M + 1] for i in range 0 to n]
j के लिए 0 से M + 1 की सीमा में, करें
table[0, j] := |j - arr[0]|
i के लिए 1 से n की सीमा में, करें
j के लिए 0 से M + 1 की सीमा में, करें
table[i, j] := 100000000
k के लिए (j-target और 0) के अधिकतम और (M और j + target) के न्यूनतम की सीमा में, करें
table[i,j] = table[i,j], table[i - 1,k] + |arr[i] - j| का न्यूनतम
ans := 10000000
j के लिए 0 से M + 1 की सीमा में, करें
ans = ans और table[n-1, j] का न्यूनतम
ans वापस करें
उदाहरण
बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
M = 100 def get_min_cost(arr, target): n = len(arr) table = [[0 for i in range(M + 1)] for i in range(n)] for j in range(M + 1): table[0][j] = abs(j - arr[0]) for i in range(1, n): for j in range(M + 1): table[i][j] = 100000000 for k in range(max(j - target, 0), min(M, j + target) + 1): table[i][j] = min(table[i][j], table[i - 1][k] + abs(arr[i] - j)) ans = 10000000 for j in range(M + 1): ans = min(ans, table[n - 1][j]) return ans arr= [56, 78, 53, 62, 40, 7, 26, 61, 50, 48] target = 20 print(get_min_cost(arr, target))
इनपुट
[56, 78, 53, 62, 40, 7, 26, 61, 50, 48], 20
आउटपुट
35
