Динамическое программирование

Задача о рюкзаке

Дано 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(n) = min(F(n - a_1), F(n - a_2),\cdots, F(n - a_k)) + 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.

Ссылки на материалы по теме

Задачи