Дано N предметов массой m1, …, mN и стоимостью c1, …, cN соответственно. Ими наполняют рюкзак, который выдерживает вес не более M. Какую наибольшую стоимость могут иметь предметы в рюкзаке?
Эта задача является частным случаем задачи об укладке рюкзака, которая в общем случае формулируется, как:
Дано n предметов, i-й предмет имеет массу weighti > 0 и стоимость costi > 0. Необходимо выбрать из этих предметов такой набор, чтобы суммарная масса не превосходила заданной величины M (вместимость рюкзака), а суммарная стоимость была максимальна. Другими словами, нужно определить набор бинарных величин (b1, b2,..., bn), при котором выполняется соотношение:
\[\begin{aligned} b_1 \cdot weight_1 & + b_2 \cdot weight_2 + \cdots + b_n \cdot weight_n \le M \\ \text{и сумма } b_1 \cdot cost_1 & + b_2 \cdot cost_2 + \cdots + b_n \cdot cost_n \text{ максимальна} \end{aligned} \]
Введем функцию A. A(n, m) - максимальная стоимость предметов, которые можно уложить в рюкзак максимальной вместимости m, если можно использовать только первые n предметов из заданных N.
Зададим краевые значения для A(n, m)
Если ни один предмет брать нельзя, т.е. n = 0, то A(0, m) = 0, для любого m.
Если вместимость рюкзака равна 0, т.е. m = 0 , то A(n, 0) = 0, для любого n.
\[\begin{aligned}
n=0, \text{тогда } \forall m \quad & \Rightarrow A(0, m) = 0 \\
m = 0, \text{тогда } \forall n \quad & \Rightarrow A(n, 0) = 0
\end{aligned} \]
Теперь составим рекуррентное соотношение. Необходимо из предметов с номерами 1, ..., n составить рюкзак максимальной стоимости, чей вес не превышает m. При этом возможно два случая: когда в максимальный рюкзак включен предмет с номером n и когда предмет n не попал в максимальный рюкзак.
Если предмет n не попал в максимальный рюкзак массы m, то максимальный рюкзак будет составлен только из предметов с номерами 1, ..., n - 1, следовательно, A(n, m) = A(n - 1, m).
Если же в максимальный рюкзак включен предмет n, то масса оставшихся предметов не превышает m - weightn, а от добавления предмета n общая стоимость рюкзака увеличивается на costn. Значит, A(n, m) = A(n - 1, m - weightn) + costn. Теперь из двух возможных вариантов составить рюкзак массы, не превосходящей m, из предметов 1, ..., n нужно выбрать наилучший, т.е.
\[
max(A(n - 1, m),\quad A(n - 1, m - weight_n) + cost_n)
\]
В программе веса предметов считаем в список weight, а стоимости в список cost. Т.к. принято индексировать массивы начиная с индекса 0, то чтобы у нас weight[1] и cost[1] соответствовали предмету с номером 1, то после считывания добавим фиктивный предмет с весом 0 и стоимостью 0. Значения функции A(n,m) будем хранить в списке A[n][m]. Ответ на задачу будет находится в элементе A[N][M].
Примерный код программы:
N, M = map(int, input().split()) # N - количество предметов
# M - предельная масса
weight = [int(i) for i in input().split()] # веса
cost = [int(i) for i in input().split()] # стоимости
weight.insert(0, 0)
cost.insert(0, 0)
A = []
for i in range(N+1):
A.append([0]*(M+1))
for n in range(1, N+1):
for m in range(M+1):
A[n][m] = A[n-1][m]
if (m >= weight[n] and A[n-1][m-weight[n]] + cost[n] > A[n][m]):
A[n][m] = A[n-1][m-weight[n]] + cost[n]
print(A[N][M])
Рассмотрим пример:
4 6
2 4 1 2
7 2 5 1
| Предельный вес (m) | ||||||||
|---|---|---|---|---|---|---|---|---|
| Кол-во предметов | 0 | 1 | 2 | 3 | 4 | 5 | 6 | |
| weight = 0 cost = 0 | n = 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| weight = 2 cost = 7 | n = 1 | 0 | 0 | 7 | 7 | 7 | 7 | 7 |
| weight = 4 cost = 2 | n = 2 | 0 | 0 | 7 | 7 | 7 | 7 | 9 |
| weight = 1 cost = 5 | n = 3 | 0 | 5 | 7 | 12 | 12 | 12 | 12 |
| weight = 2 cost = 1 | n = 4 | 0 | 5 | 7 | 12 | 12 | 13 | 13 |
Теперь нам нужно вывести список номеров предметов, которые будут входить в максимальный рюкзак.
def print_answer(n, m):
# n предметов
# m предельная масса
if A[n][m] == 0:
return
elif A[n-1][m] == A[n][m]:
print_answer(n-1, m)
else:
print_answer(n-1, m - weight[n])
print(n, end = " ")
В обороте находятся банкноты k различных номиналов: a1, a2, ..., ak рублей. Банкомат должен выдать сумму в N рублей при помощи минимального количества банкнот или сообщить, что запрашиваемую сумму выдать нельзя. Будем считать, что запасы банкнот каждого номинала неограничены.
Пусть F(n) -- минимальное количество банкнот, которым можно заплатить сумму в n рублей. Очевидно, что F(0) = 0, F(a1) = F(a2) =...= F(ak) = 1. Если некоторую сумму n невозможно выдать, будем считать, что F(n) = (бесконечность).
Выведем рекуррентную формулу для F(n), считая, что значения F(0), F(1), ..., F(n - 1) уже вычислены. Как можно выдать сумму n? Мы можем выдать сумму n - a1, а потом добавить одну банкноту номиналом a1. Тогда нам понадобится F(n - a1) + 1 банкнота. Можем выдать сумму n - a2 и добавить одну банкноту номиналом a2, для такого способа понадобится F(n - a2) + 1 банкнота и т. д. Из всевозможных способов выберем наилучший, то есть:
В итоге в элементе F[S] - будет ответ, т.е. минимальное количество банкнот, которыми можно выдать номинал S.
Запишем код программы:
N = int(input()) # количество номиналов банкнот в обращении
nominal = [int(i) for i in input().split()] # номиналы банкнот
S = int(input()) # сумма, которую нужно выдать
F = []
F.append(0)
for m in range(1, S+1):
F.insert(m, float("+inf"))
for i in range(len(nominal)):
if m >= nominal[i] and F[m-nominal[i]] + 1 < F[m]:
F[m] = F[m - nominal[i]] + 1
print(F[S])
Если нам нужно вывести еще и сами номиналы банкнот, как это можно сделать? Рассмотрим все номиналы банкнот и значения n - a1, n - a2, ..., n - ak. Если для какого-то i окажется, что F(n - ai) = F(n) - 1, значит, мы можем выдать банкноту в ai рублей и после этого свести задачу к выдаче суммы n - ai, и так будем продолжать этот процесс, пока величина выдаваемой суммы не станет равна 0.