ПОМОГИТЕ ПРОШУ С++
Дан набор гирек массой m1......mn . Можно ли их разложить на две чаши весов таким образом, чтобы они оказались в равновесии?
Входные данные
4
4 2 3 1
Результат работы
YES
#include <iostream>
#include <vector>
#include <numeric>
bool canBalanceWeights(const std::vector<int>& weights) {
int total = std::accumulate(weights.begin(), weights.end(), 0);
// Если общая масса нечетная, не можем разделить на две равные части
if (total % 2 != 0) {
return false;
}
int target = total / 2;
int n = weights.size();
// Создаем массив для динамического программирования
std::vector<bool> dp(target + 1, false);
dp[0] = true; // 0 можно получить, не беря ни одной гирьки
for (int weight : weights) {
for (int j = target; j >= weight; --j) {
dp[j] = dp[j] || dp[j - weight];
}
}
return dp[target];
}
int main() {
int n;
std::cout << "Введите количество гирек: ";
std::cin >> n;
std::vector<int> weights(n);
std::cout << "Введите массы гирек: ";
for (int i = 0; i < n; ++i) {
std::cin >> weights[i];
}
if (canBalanceWeights(weights)) {
std::cout << "YES" << std::endl;
} else {
std::cout << "NO" << std::endl;
}
return 0;
}
def can_balance(weights):
total_weight = sum(weights)
# Если общая масса нечетная, не можем поделить на два равных
if total_weight % 2 != 0:
return "NO"
target = total_weight // 2
n = len(weights)
# Массив динамического программирования
dp = [False] * (target + 1)
dp[0] = True # масса 0 возможна без вытаскивания гирек
for weight in weights:
# Идем от высокой к низкой, чтобы не переписывать текущие состояния
for j in range(target, weight - 1, -1):
dp[j] = dp[j] or dp[j - weight]
return "YES" if dp[target] else "NO"
# Пример использования
weights = [4, 2, 3, 1]
result = can_balance(weights)
print(result) # Вывод: YES
