Определить сколько максимум денег может заработать продавец

@fedor222 · Регистрация: 25.04.2019

Студворк — интернет-сервис помощи студентам

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

В универе задали вот такую задачу :
Продавец книг заметил что если клиенту предложит правильную цену за книгу тогда он её купит. По одежде он оценивал денежнок состояние клиета . Если денежное состояние p а цена книги k то предложенная цена должна бвть pk.
Во время чрмарки очень много клинетов продавец не успевал посмотреть все книги а выбирал одну из 3 верхних в куче.
Дано n книг и поле цен h книг [ h₁ , h₂ ... h_n] и поле денежного состояния клиента [ p₁ , p₂ ... p_n] . Сколько максимум денег может заработать продавец.
n ≤ 500 и 1 ≤ hi ≤ 1000 и 1 ≤ pi ≤ 1000.

Пример: Ответ:
n = 4 336
h = [16, 6, 2, 10]
p = [3, 8, 12, 9]

первому клиенту мы даем третью книгу сверху со стоимостью 2, зв которую он заплатит 6 . У нас остаются книги со стоимостью 16, 6, 10 ( в этом порядке) . второму покупателю лаем вторую книгу сверху за которую он заплатит 6*8 = 48 . Остаются книги 16 и 10 . Третьему предлагаем самую верхнюю книгу и получаем 16*12 = 192. и последний забирает последнюю книгу за 90. и общая сумма 336.

Вот такая задача.
Уже несколько дней сижу думаю над алгоритмом и получилось придумать только аналог бэктрекинга.

Написанно в питоне, p это список покупателей k это список цен книг , я его уменьшаю во время рекурсии и i это индекс клиента в списке. Вот только такое решение не посчитает при n = 20 а надо до 500 .

Python

def back_tracking_riesenie(p, k, i):
    if len(k) == 1:
        vysl = p[i] * k[0]
        return vysl
    k1 = k[1:]
    k2 = [k[0]]
    [k2.append(i) for i in k[2:]]
    if len(k) == 2:
        vysl1 = p[i] * k[0] + back_tracking_riesenie(p, k1, i + 1)
        vysl2 = p[i] * k[1] + back_tracking_riesenie(p, k2, i + 1)
        return max(vysl1, vysl2)
 
    if str([[k[0], k[1], [k[2]]]]) in pole[i]:
        return pole[i].get([k[0], k[1], [k[2]]])
 
    k3 = k[:2]
    [k3.append(i) for i in k[3:]]
    vysl1 = p[i] * k[0] + back_tracking_riesenie(p, k1, i + 1)
    vysl2 = p[i] * k[1] + back_tracking_riesenie(p, k2, i + 1)
    vysl3 = p[i] * k[2] + back_tracking_riesenie(p, k3, i + 1)
 
    vysl = max(vysl1, vysl2, vysl3)
    pole[i][str([k[0], k[1], [k[2]]])] = vysl
    return vysl

	22.11.2021, 17:37

Опции темы