Новогодние скидки

@Иван Мелков · Регистрация: 27.10.2019

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

Новогодние скидки
В течении всех новогодних праздников в компьютерном супермаркете действует акция "Новогодние скидки". Для каждого из N видов товара известны его обычная цена и цена в акции. Какую наибольшую суммарную скидку получим, потратив сумму, не превышающую M, если каждый товар можно приобрести только в единственном экземпляре?

Формат входных данных
Числа N и M в первой строке, в последующих N строках пары чисел – обычная цена и цена в акции товаров. Все числовые значения натуральные, M ≤ 1000, остальные значения не превышают 100.

Формат результата
Ответ к задаче.
Помогите пожалуйста!

@_Ivana · 28.10.2019, 10:50

C++

int n, m, p[101], d[101], dp[1001][101];
 
int f(int s, int i) {
    if (s<0) return -20000; else if (i>n) return 0;
    if (!dp[s][i]) dp[s][i] = std::max(f(s, i+1), p[i]-d[i]+f(s-d[i], i+1));
    return dp[s][i];
}
int main () {
    std::cin >> n >> m;
    for (int i=0; i<n; i++) { std::cin >> p[i] >> d[i]; }
    std::cout << (m<=0 ? 0 : f(m, 0));
}

@Иван Мелков · 28.10.2019, 11:14 **[ТС]**

Большое спасибо!

Добавлено через 2 минуты
Если есть возможность можете пожалуйста объяснить решение?

@Иван Мелков 0 / 0 / 0 Регистрация: 27.10.2019 Сообщений: 11
		1
	Новогодние скидки 28.10.2019, 00:18. Показов 1876. Ответов 2 Метки нет (Все метки) Новогодние скидки В течении всех новогодних праздников в компьютерном супермаркете действует акция "Новогодние скидки". Для каждого из N видов товара известны его обычная цена и цена в акции. Какую наибольшую суммарную скидку получим, потратив сумму, не превышающую M, если каждый товар можно приобрести только в единственном экземпляре? Формат входных данных Числа N и M в первой строке, в последующих N строках пары чисел – обычная цена и цена в акции товаров. Все числовые значения натуральные, M ≤ 1000, остальные значения не превышают 100. Формат результата Ответ к задаче. Помогите пожалуйста! 0

@Иван Мелков 0 / 0 / 0 Регистрация: 27.10.2019 Сообщений: 11
	28.10.2019, 11:14 [ТС]	3
	Большое спасибо! Добавлено через 2 минуты Если есть возможность можете пожалуйста объяснить решение? 0

Новогодние скидки

Решение