Добавлен: 07.11.2023
Просмотров: 27
Скачиваний: 2
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Министерство образования и науки РФ
Федеральное государственное бюджетное образовательное учреждение высшего образования
«Омский государственный технический университет»
Кафедра «Информатика и вычислительная техника»
Отчёт по лабораторной работе № 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();
}
}
Результат:
