Mail.ruПочтаМой МирОдноклассникиВКонтактеИгрыЗнакомстваНовостиКалендарьОблакоЗаметкиВсе проекты

ПОМОГИТЕ ПРОШУ С++

Leyla Nuriyeva Ученик (174), открыт 8 часов назад
Дан набор гирек массой m1......mn . Можно ли их разложить на две чаши весов таким образом, чтобы они оказались в равновесии?

Входные данные

4
4 2 3 1
Результат работы

YES
2 ответа
Кирилл Пирошкин Знаток (390) 8 часов назад
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
Leyla NuriyevaУченик (174) 8 часов назад
извините , но это не с++(((
Кирилл ПирошкинЗнаток (390) 8 часов назад
ОЙ ЩА
Кирилл ПирошкинЗнаток (390) 8 часов назад
#include <iostream>
#include <vector>
#include <numeric> // для std::accumulate

std::string canBalance(const std::vector<int>& weights) {
int totalWeight = std::accumulate(weights.begin(), weights.end(), 0);

// Если общая масса нечетная, не можем поделить на две равные части
if (totalWeight % 2 != 0) {
return "NO";
}

int target = totalWeight / 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];
}
}
Кирилл ПирошкинЗнаток (390) 8 часов назад
return dp[target] ? "YES" : "NO";

}



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];

}



std::string result = canBalance(weights);

std::cout << result << std::endl; // Вывод результата



return 0;

}
Папизи Профи (878) 8 часов назад
#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;
}
Похожие вопросы