Задача: "Арбузы"

Две машины заполнены арбузами. В одной машине N (1<N<50) арбузов, а в другой - M (1<M<50). Вес каждого арбуза известен. Сколько арбузов необходимо перенести с одной машины в другую и наоборот, чтобы общий вес арбузов в одной машине сравнялся с общим весом арбузов в другой машине. Число переносов должно быть минимальным.

Например, если в первой машине находится четыре арбуза весом 7, 2, 5, 4 кг, их общий вес составляет 18 кг. Во второй машине три арбуза весом 3, 3, 5 кг с общим весом в 12 кг. Для решения этой задачи необходимо перенести арбуз в 7 кг из первой машины во вторую машину, а из второй машины арбуз в 4 кг перенести в первую. В итоге будет по 15 кг.

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

Вход: Выход:
7 2 5 4 7
4 3 5 4

Помогите пожалуйста с такой сложной задачей.

0

Понятия динамическое программирование, очередь знакомы?

0

Сообщение от valeriikozlov Понятия динамическое программирование, очередь знакомы?

Динамическое я так понял вы имеете в виду динамические типы данных (чучуть знаю) чтобы не нагружать сильно компьютер, а очередь не догадываюсь что такое. Помогите пожалуйста

0

а про массивы что-нибудь знаете?
код писать не буду (написанный мною код не принесет Вам никакой пользы). если есть желание, могу описать алгоритм решения задачи, но для этого Вы должны знать как минимум про очереди и структуры.
Почитайте пор стеки, очереди и структуры, как все станет с ними понятно можно будет решить эту задачу.

0

я изначально думал просто через массив, но алгоритм составить не получается, просто сравнивать все элементы вместе это нужно 100 циклов, потом ещё возможен перенос только одного арбуза из одной машины. помогите с непонятным алгоритмом, записать в коде не проблема

Добавлено через 4 минуты

Сообщение от BBoyXaker Вход: Выход: 7 2 5 4 7 4 3 5 4

Вот как должно быть:
Вход:
тест 1: 7 2 5 4
тест 2: 4 3 5
Выход:
тест 1: 7
тест 2: 4

0

Сообщение от BBoyXaker помогите с непонятным алгоритмом, записать в коде не проблема

В условии ограничений на вес арбузов нет, поэтому я сам определю например так: вес арбуза не превышает 20 кг, соответственно общий вес арбузов не превышает 2000 кг.
Создаем массив a[0..2000] все значения которых изначально делаем например 200. Каждое значение этого массива будет меняться в процессе выполнения программы и будет означать вот что: например a[4]=10, это значит что чтобы достичь в первой машине веса 4 кг, нужно будет переместить 10 арбузов (неважно из какой машины сколько и каких именно).
Затем создаем массив b[1..20] (мы договорились что вес арбузов не превышает 20 кг) в котором запишем сколько каких арбузов есть в обеих машинах. Например b[3]=4 означает что арбузов с весом 3 в обоих машинах всего четыре.
Затем создаем структуру в которой будет всего один массив (такой же как массив b[]), и на основе этой структуры создаем массив таких структур размером [0..2000] (пусть это будет массив c[1..2000]). Каждый элемент этого массива будет содержать информацию о том сколько каких арбузов содержится в первой машине. Т.е. в c[5] можно узнать при весе в первой машине 5 кг, сколько каких арбузов в первой машине есть. (Можно в эту структуру включить и данные из массива a[], но необязательно, я намеренно разделил их чтобы понятнее было объяснить)
Теперь так, суммируем все арбузы в первой машине (пусть получилось X кг). Тогда a[X] делаем равным 0 (чтобы достичь в первой машине X кг нужно перенести 0 арбузов). Записываем все имеющиеся арбузы в c[X]. И заносим значение X в очередь.
Далее обрабатываем элементы очереди так:
Берем очередной номер Y из очереди. Перебирая имеющиеся арбузы в c[Y] и учитывая все имеющиеся арбузы в b[] смотрим улучшаем (уменьшаем) ли значение в массиве a[]. Например очередной элемент в очереди 20 и a[20]=3 (еще раз напомню это значит что чтобы сделать в первой машине 20 кг нужно переложить 3 арбуза). Смотрим имеющиеся арбузы в первой машине для 20 кг и учитывая все имеющиеся арбузы мы например можем убрать из первой машины арбуз весом 3 кг. Тогда смотрим значение a[17]. Если это значение больше чем a[20]+1 , то записываем в a[17] значение a[20]+1. Арбузы из c[20] переписываем в c[17] (без одного арбуза весом 3 кг). И заносим 17 в очередь.
Аналогично для добавления арбуза весом 3 кг в первую машину, делаем тоже самое для a[23] и c[23] (только туда добавляем еще один арбуз весом 3 кг).
В общем такой алгоритм. )

1

valeriikozlov, Спасибо большое

0