Здесь мы разберем решение задачи "Копилка".

Задан вес E пустой копилки и вес F копилки с монетами. В копилке могут находиться монеты N видов, для каждого вида известна ценность P_i и вес W_i одной монеты. Найти минимальную и максимальную суммы денег, которые могут находиться в копилке.
Ограничения: 1 ≤ E ≤ F ≤ 100, 1 ≤ N ≤ 50, 1 ≤ P_i ≤ 500, 1 ≤ W_i ≤ 100, все числа целые, время 2с. [1].

В копилке находятся монеты весом f-e. Для хранения суммы цены монет (максимальной или минимальной) будем использовать массив sum. В i-й ячейки этого массива будет храниться ценность монет (максимальная или минимальная) при весе равном i. Элементов в массиве будет f-e. При этом нужно учитывать, что вес не всех монет меньше i. В некоторых случаях при таком весе копилка вообще не может быть заполнена. При каждом весе нужно проверять – может ли эта монета вообще быть в копилке (вес монеты должен быть не больше i). При этом, если эта монета может быть в копилке, нужно просматривать, какие из монет могут находить в копилке помимо этой, то есть при весе i-w[j], где w[j] вес данной монеты. Но сумма при таком весе считалась ранее. Если же при этом весе (i-w[j]) копилка не могла быть заполнена, то монету j не следует помещать в копилку. Если же она может быть помещена, то нужно найти сумму денег, которая при этом находится в копилке, то есть sum[i-w[j]]+p[j]. Далее нужно взять монету следующего вида и также найти сумму денег (если эта монета может находиться в копилке). А в зависимости от того, что ищем - максимальную или минимальную сумму денег, выбираем одну из сумм. Затем эту сумму помещаем в i-ю ячейку массива sum. Так продолжается до тех пор, пока i не станет равной f-e. Искомая сумма будет находиться в ячейке sum[f-e]. При этом можно также найти виды и количество монет, которые помешены в копилку. Для этого организован двумерный массив lo. В каждой строке этого массива храниться информация о том, какие именно монеты взяты при данном весе i. Заполнение этого двумерного массива происходит следующим образом: после того как узнали, какую именно монету положили в копилку, считается значение элементов строки матрицы lo. Элементам строки i присваиваются элементы строки i-w[j], где w[j] вес той монеты, которую поместили в копилку. При этом к элементу lo[i, j] прибавляется единица, так как взяли эту монету. Вот таким образом происходит заполнение матрицы lo. При этом последняя строка матрицы будет показывать, какие монеты взяты при данном значении суммы.

Решение вы можете посмотреть здесь.

⁽¹⁾Меньшиков Ф.В. Олимпиадные задачи по программированию. - СПб: Питер, 2006. - 315с.

Предыдущий шаг Содержание