資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究在 C++ 中查詢陣列的最小調整成本
概念
對於給定的正整數陣列，我們替換陣列中的每個元素，使得陣列中相鄰元素之間的差小於或等於給定的目標值。現在，我們的任務是最小化調整成本，即新舊值之間差異的總和。因此，我們基本上需要最小化 Σ|A[i] – Anew[i]|，其中 0 ≤ i ≤ n-1，n 表示 A[] 的大小，Anew[] 表示相鄰差小於或等於目標值的陣列。假設陣列的所有元素都小於常數 M = 100。
輸入
arr = [56, 78, 53, 62, 40, 7, 26, 61, 50, 48], target = 20
輸出
Minimum adjustment cost is 35
方法
為了最小化調整成本 Σ|A[i] – Anew[i]|，對於陣列中的所有索引 i，我們記住 |A[i] – Anew[i]| 應儘可能接近零。需要注意的是，
|A[i] – Anew[i+1] ]| ≤ 目標值。
這裡，這個問題可以透過動態規劃 (DP) 來解決。
假設 dp1[i][j] 表示將 A[i] 更改為 j 的最小調整成本，則 DP 關係定義為：
dp1[i][j] = min{dp1[i - 1][k]} + |j - A[i]|
對於所有滿足 |k - j| ≤ 目標值的 k。
在這種情況下，0 ≤ i ≤ n 且 0 ≤ j ≤ M，其中 n 是陣列中元素的數量，M = 100。因此，所有 k 值都以這種方式考慮，使得 max(j – 目標值, 0) ≤ k ≤ min(M, j + 目標值)。最後，陣列的最小調整成本將是 min{dp1[n – 1][j]}，對於所有 0 ≤ j ≤ M。
示例
// C++ program to find minimum adjustment cost of an array
#include <bits/stdc++.h>
using namespace std;
#define M1 100
//Shows function to find minimum adjustment cost of an array
int minAdjustmentCost(int A1[], int n1, int target1){
// dp1[i][j] stores minimal adjustment cost on changing
// A1[i] to j
int dp1[n1][M1 + 1];
// Tackle first element of array separately
for (int j = 0; j <= M1; j++)
dp1[0][j] = abs(j - A1[0]);
// Perform for rest elements of the array
for (int i = 1; i < n1; i++){
// Now replace A1[i] to j and calculate minimal adjustment
// cost dp1[i][j]
for (int j = 0; j <= M1; j++){
// We initialize minimal adjustment cost to INT_MAX
dp1[i][j] = INT_MAX;
// We consider all k such that k >= max(j - target1, 0)
and
// k <= min(M1, j + target1) and take minimum
for (int k = max(j-target1,0); k <= min(M1,j+target1);
k++)
dp1[i][j] = min(dp1[i][j], dp1[i - 1][k] + abs(A1[i] -j));
}
}
//Now return minimum value from last row of dp table
int res1 = INT_MAX;
for (int j = 0; j <= M1; j++)
res1 = min(res1, dp1[n1 - 1][j]);
return res1;
}
// Driver Program to test above functions
int main(){
int arr1[] = {56, 78, 53, 62, 40, 7, 26, 61, 50, 48};
int n1 = sizeof(arr1) / sizeof(arr1[0]);
int target1 = 20;
cout << "Minimum adjustment cost is "
<< minAdjustmentCost(arr1, n1, target1) << endl;
return 0;
}輸出
Minimum adjustment cost is 35
更新於: 2020-07-25
359 次瀏覽
廣告