資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++程式：獲取拼圖碎片之間最小差值
假設我們有一個包含m個元素的陣列A和另一個數字n。Amal決定給他n個朋友送禮物，所以他會給每人一個拼圖。店員告訴他店裡有m個拼圖，但它們的難度和尺寸可能不同。具體來說，第i個拼圖包含A[i]塊。所以Amal決定他禮物中拼圖塊數的差值必須儘可能小。設x是他購買的最大拼圖的塊數，y是最小拼圖的塊數。他希望選擇n個拼圖，使x - y儘可能小。我們必須找到x - y的最小可能值。
問題類別
上述問題可以透過應用貪心演算法解決。貪心演算法是一種選擇當前最佳解決方案而不是遍歷所有可能解決方案的演算法。貪心演算法也用於解決最佳化問題，就像它的“大哥”動態規劃一樣。在動態規劃中，需要遍歷所有可能的子問題才能找到最優解，但這有一個缺點：它需要更多的時間和空間。因此，在各種情況下，貪心演算法被用來找到問題的最優解。雖然它並非在所有情況下都能提供最優解，但如果設計仔細，它可以比動態規劃更快地產生解。貪心演算法為最佳化問題提供區域性最優解。這種技術的例子包括克魯斯卡爾和普里姆最小生成樹(MST)演算法、霍夫曼樹編碼、迪傑斯特拉單源最短路徑問題等。
https://tutorialspoint.tw/data_structures_algorithms/greedy_algorithms.htm
https://tutorialspoint.tw/data_structures_algorithms/dynamic_programming.htm
因此，如果我們問題的輸入類似於A = [10, 12, 10, 7, 5, 22]；n = 4，那麼輸出將是5，因為有4個朋友。商店出售6個拼圖。如果Amal購買前四個拼圖，分別包含10、12、10和7塊，那麼最大和最小拼圖尺寸之間的差值為5。不可能得到更小的差值。
步驟
為了解決這個問題，我們將遵循以下步驟：
ans := 1000 m := size of A sort the array A for initialize i := n - 1, when i < m, update (increase i by 1), do: ans := minimum of ans and (A[i] - A[i - (n - 1)]) return ans
示例
讓我們看看下面的實現以更好地理解：
#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> A, double n){
int ans = 1000;
int m = A.size();
sort(A.begin(), A.end());
for (int i = n - 1; i < m; i++)
ans = min(ans, A[i] - A[i - (n - 1)]);
return ans;
}
int main(){
vector<int> A = { 10, 12, 10, 7, 5, 22 };
double n = 4.;
cout << solve(A, n) << endl;
}輸入
{ 10, 12, 10, 7, 5, 22 }, 4輸出
5
224 次瀏覽
