पायथन में एक सरणी की न्यूनतम समायोजन लागत पाएं

मान लीजिए कि हमारे पास धनात्मक संख्याओं की एक सरणी है; हम उस सरणी सरणी से प्रत्येक तत्व को प्रतिस्थापित करते हैं ताकि सरणी में दो आसन्न तत्वों के बीच का अंतर किसी दिए गए लक्ष्य से कम या बराबर हो। अब, हमें समायोजन लागत को कम करना होगा, इसलिए नए मूल्य और पुराने मूल्य के बीच अंतर का योग। अधिक सटीक रूप से, हम ∑|A[i] - Anew[i]| . को छोटा करते हैं जहाँ मैं 0 से n-1 की सीमा में, यहाँ n को A के आकार के रूप में दर्शाया गया है और Anew वह सरणी है जिसका आसन्न अंतर लक्ष्य से कम या उसके बराबर है।

इसलिए, यदि इनपुट [56, 78, 53, 62, 40, 7, 26, 61, 50, 48], लक्ष्य =20 जैसा है, तो आउटपुट 25

होगा।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

n :=गिरफ्तारी का आकार
तालिका :=[[0 के लिए मैं 0 से एम + 1 की सीमा में] के लिए मैं 0 से n की सीमा में]
j के लिए 0 से M + 1 की सीमा में, करें
- टेबल[0, जे] :=|j - arr[0]|
1 से n की सीमा में i के लिए, करें
- j के लिए 0 से M + 1 की सीमा में, करें
  - टेबल [i, j] :=100000000
  - k के लिए अधिकतम (j-लक्ष्य और 0) और न्यूनतम (M और j + लक्ष्य) की सीमा में, करें
    - तालिका[i,j] =न्यूनतम तालिका[i,j], तालिका[i - 1,k] + |arr[i] - j|
उत्तर :=10000000
j के लिए 0 से M + 1 की सीमा में, करें
- ans =न्यूनतम उत्तर और तालिका [n-1, j]
- वापसी उत्तर

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

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