Министерство образования и науки РФФедеральное государственное бюджетное образовательное учреждение высшего образования«Омский государственный технический университет»Кафедра «Информатика и вычислительная техника»Отчёт по лабораторной работе № 7по дисциплине«Проектирование и тестирование программного обеспечения»

Выполнил Студент гр. ПИ-212 Шарф А.А ______________ (подп., дата) Проверил Старший преподаватель каф. ИВТ Карабцов Р.Д. (подп., дата)

Омск, 2023Задача 7.4:Перетягивание каната - это состязание в грубой силе, когда две группы людей тянут канат в противоположные стороны. Та команда, которая сумела утянуть канат в свою сторону, объявляется победителем.На корпоративном пикнике решили посостязаться в перетягивании каната. Участников пикника нужно честно разбить на две команды. Каждый человек должен попасть в одну или другую команду, число человек в одной команде не должно превышать число человек в другой более чем на одного, и суммарные веса людей каждой команды должны быть близки, насколько это возможно.Входные данныеВходные данные начинаются со строки, содержащей одно положительное целое число, которое означает количество тестовых блоков, за которой следует пустая строка.Первая строка каждого блока содержит n, число участников пикника. Каждая из следующих n строк содержит вес одного из участников пикника

---

, причем вес задается целым числом между 1 и 450. Число участников пикника не превышает 100.

Между двумя последовательными тестовыми блоками также находится пустая строка.
Выходные данные

Для каждого тестового блока вы должны вывести строку, содержащую два числа: суммарный вес людей в одной команде и суммарный вес людей в другой команде. Если эти числа отличны, выведите сначала меньшее.

Выходные данные для двух последовательных блоков должны быть разделены пустой строкой.

Пример входных данных

1
3

100

90

200
Соответствующие выходные данные

190 200

Код:

#include

#include

#include

#include

#include

using namespace std;
int N;

int W[100 + 5];

long long dp[450 * 100 + 5];
void solve()

{

int sum = accumulate(W + 1, W + N + 1, 0);

memset(dp, 0, sizeof(dp));

dp[0] = 1 << 0;
for (int i = 1; i <= N; ++i)

for (int j = sum; j >= 0; --j)

if (dp[j])

dp[j + W[i]] |= dp[j] << 1;
int minDiff = 450 * 100;

int teamOneWeight = 0, teamTwoWeight = 0;

for (int i = 0; i <= sum; ++i)

if (dp[i] & (1ll << (N / 2)))

{

int diff = abs(i - (sum - i));

if (diff < minDiff)

{

minDiff = diff;

teamOneWeight = min(i, sum - i);

teamTwoWeight = max(i, sum - i);

}

}

cout << teamOneWeight << " " << teamTwoWeight << endl;

}
int main()

{

int T, Case = 0;

cin >> T;

while (T--)

{

cin >> N;

for (int i = 1; i <= N; ++i)

cin >> W[i];
if (++Case > 1)

cout << endl;

solve();

}

}

Результат:

---

Смотрите также файлы

• Курсовая работа по специальности Инвестиции на тему Особенности инвестиционной политики России.doc

• Тема. Электроснабжение завода тяжелого машиностроения.docx

• основы информационной безопасности.pdf

• Теоретическая важность.docx

• 1. Анализ доходов и расходов бюджета Фонда социального страхования рф 3.docx