Дискретный и повторный выбор элемента
В отличие от задачи о рюкзаке 0/1, в неограниченном рюкзаке нам разрешено использовать неограниченное количество экземпляров предмета.
Учитывая вес рюкзака A и набор предметов с определенным значением B[i] и весом C[i], нам нужно вычислить максимальное количество, которое могло поместиться в этом количестве.
A = 10 B = [6, 7] C = [5, 5] OP = 14
Мы хотим найти максимальное накопленное значение для каждого подмассива и для каждого возможного веса. Для каждой возможной емкости ‘a’ (0‹=a‹=A) у нас есть два варианта.
- Исключить элемент, в этом случае мы возьмем любую прибыль, которую получим от подмассива, исключая этот элемент.
- Включить предмет, если вес меньше доступного веса ранца, при этом мы получаем стоимость этого предмета плюс значения, собранные из оставшейся емкости.
Наконец, мы берем максимум из обоих.
Реализация кода
def solve(A, B, C):
n = len(B)
dp = [0 for i in range(A + 1)]
for i in range(A + 1):
for j in range(n):
if (C[j] <= i):
dp[i] = max(dp[i], dp[i - C[j]] + B[j])
return dp[A]
Резка стержня
Учитывая стержень длины N единиц и массив A размера N, обозначают цены, которые содержат цены всех частей размером от 1 до N. Найдите и верните максимальную стоимость, которую можно получить, разрезав стержень и продав его части.
def solve( A):
n = len(A)
dp = [0] * (n+1)
for i in range(1, n+1):
for j in range(i):
dp[i] = max(dp[i], A[j] + dp[i-j-1])
return dp[n]
Размен монет I
Вам дан целочисленный массив coins, представляющий монеты разного номинала, и целочисленный массив amount, представляющий общую сумму денег. Верните наименьшее количество монет, необходимое для получения этой суммы. Если эту сумму денег нельзя компенсировать ни одной комбинацией монет, верните -1. Вы можете предположить, что у вас есть бесконечное количество монет каждого вида.
Реализация кода
def coinChange(coins, amount):
if amount == 0:
return 0
if amount in coins:
return 1
max_ = math.inf
dp = [max_]*(amount+1)
dp[0] = 0
dp[1] = 1 if 1 in coins else -1
for i in range(1, amount+1):
if i in coins:
dp[i] = 1
else:
min_num_coins = max_
for coin in coins:
if i >= coin:
min_num_coins = min(dp[i-coin] + 1, \
min_num_coins)
dp[i] = min_num_coins
return dp[-1] if dp[-1] != max_ else -1
Размен монет II
Вам дан целочисленный массив coins, представляющий монеты разного номинала, и целочисленный массив amount, представляющий общую сумму денег. Возвращает количество комбинаций, составляющих эту сумму. Если эту сумму денег нельзя компенсировать ни одной комбинацией монет, вернуть 0. Вы можете предположить, что у вас есть бесконечное количество монет каждого вида. Ответ гарантировано соответствует 32-разрядному целому числу со знаком.
Реализация кода
def change(amount, coins):
l = len(coins)
dp = [0] * (amount + 1)
dp[amount] = 1
for i in range(l-1, -1, -1):
for cur_amnt in range(amount - coins[i], -1, -1):
dp[cur_amnt] += dp[cur_amnt + coins[i]]
return dp[0]
Удачного кодирования!
Дополнительные материалы на PlainEnglish.io. Подпишитесь на нашу бесплатную еженедельную рассылку новостей. Подпишитесь на нас в Twitter и LinkedIn. Посетите наш Community Discord и присоединитесь к нашему Коллективу талантов.
