資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++程式檢查給定的糖果是否可以分成重量相等的兩份
假設我們有一個包含n個元素的陣列A。Amal和Bimal從父母那裡收到了n塊糖果。每塊糖果的重量要麼是1克，要麼是2克。他們想公平地將所有糖果分給自己，以便他們糖果的總重量相同。我們必須檢查我們是否可以做到這一點。（我們不能將糖果分成兩半）。
問題類別
上述問題可以透過應用貪心問題解決技術來解決。貪心演算法技術是一種演算法型別，其中選擇當前最佳解決方案，而不是遍歷所有可能的解決方案。貪心演算法技術也用於解決最佳化問題，就像其更大的兄弟動態規劃一樣。在動態規劃中，有必要遍歷所有可能的子問題以找出最佳解決方案，但它有一個缺點；即它需要更多的時間和空間。因此，在各種情況下，使用貪心技術來找出問題的最佳解決方案。雖然它並非在所有情況下都能提供最佳解決方案，但如果設計得當，它可以比動態規劃問題更快地產生解決方案。貪心技術為最佳化問題提供區域性最優解。此技術的示例包括克魯斯卡爾和普里姆的最小生成樹 (MST) 演算法、霍夫曼樹編碼、迪傑斯特拉的單源最短路徑問題等。
https://tutorialspoint.tw/data_structures_algorithms/greedy_algorithms.htm
https://tutorialspoint.tw/data_structures_algorithms/dynamic_programming.htm
因此，如果我們問題的輸入類似於 A = [2, 1, 2, 1]，則輸出將為 True，因為我們可以將其分成 [1, 2]。
步驟
為了解決這個問題，我們將遵循以下步驟：
a := 0 b := 0 n := size of A for initialize i := 0, when i < n, update (increase i by 1), do: k := A[i] (if k is same as 1, then (increase a by 1), otherwise (increase b by 1)) if (a mod 2 is 1 OR (b mod 2 is 1 and a < 2)) then return false, otherwise true
示例
讓我們看看以下實現以更好地理解：
#include <bits/stdc++.h>
using namespace std;
bool solve(vector<int> A){
int a = 0;
int b = 0;
int n = A.size();
for (int i = 0; i < n; i++){
int k = A[i];
(k == 1 ? a++ : b++);
}
return ((a % 2 || (b % 2 && a < 2)) ? false : true);
}
int main(){
vector<int> A = { 2, 1, 2, 1 };
cout << solve(A) << endl;
}輸入
{ 2, 1, 2, 1 }輸出
1
更新於： 2022年4月7日
239 次檢視
廣告