পাইথনে অ্যারের ন্যূনতম অ্যাডজাস্টমেন্ট কস্ট বের করা

ধরা যাক একটি পজিটিভ নম্বরের অ্যারে আছে। আমরা অ্যারে-এর প্রতিটি উপাদান রিপ্লেস করব যেন দুটি সংলগ্ন উপাদানের পার্থক্য একটি দেওয়া টার্গেটের চেয়ে কম বা সমান হয়। অ্যাডজাস্টমেন্ট কস্ট হলো পুরানো এবং নতুন মানগুলোর পার্থক্যের যোগফল। আমাদের এই কস্ট ন্যূনতম করতে হবে।

যেমন, অ্যারে = [56,78,53,62,40,7,26,61,50,48], target=20 হলে আউটপুট 35।

সমাধানের ধাপসমূহ (ডাইনামিক প্রোগ্রামিং)

n := অ্যারের আকার, M := 100 (আনুমানিক সর্বোচ্চ মান)
table[n][M+1] DP টেবিল তৈরি করুন
প্রথম সারি ইніশিয়ালাইজ করুন: table[0][j] = |j - arr[0]|
বাকি সারিগুলোর জন্য: table[i][j] = min_{k ∈ [max(j-target,0), min(M, j+target)]} (table[i-1][k] + |arr[i] - j|)
উত্তর = min_{j} table[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