题目内容

商城双$11$大促销，每种商品限购两件。一共有$M$种商品。每种商品的原始价格为$X$元。买一件折扣价是$Y$元，买两件折扣价是$Z$元。其中$X>=Y>=Z$。小明银行卡里有余额$N$元。在$N$元的范围内怎么购买商品，才可以获得最多的优惠金额?

输入描述

第$1$行:商品种类$M$，$M$的范围是$[1,20]$。

题解

题面分析

在双11大促销中，商城共有 $M$ 种商品，每种商品限购两件，原始价格为 $X$ 元，购买一件的折扣价为 $Y$ 元，购买两件的折扣价为 $Z$ 元，其中满足 $X \geq Y \geq Z$。小明的银行卡余额为 $N$ 元。在不超过 $N$ 元的预算内，如何购买商品才能获得最大的优惠金额？

问题转化

本问题可以转化为 多重背包问题。具体来说：