题目内容

小美是一位购物狂人，他经常光顾提瓦特商店。最近，提瓦特商店推出了一项促销活动，有$N$件商品打折销售。每个商品都有原价和折扣价，而且不同的商品的折扣力度也不同。

小美听说了这个促销活动后非常兴奋，他计划购买尽可能多的商品，同时也希望尽量少地花钱。他掏出了自己的钱包，发现他手头有$X$元的现金和$Y$张折扣券。

于是小美找到了你，希望你能帮助他计算出在这种情况下他可以购买的最多商品数量以及花费的最少钱数。

思路

动态规划解决.背包问题

状态:

$dp[i][j][k]$ 代表在考虑前 $i$ 个物品时花费 $j$ 元且已经用掉了 $k$ 个折扣券时能买到的最多的商品.

这里用 $a[i]$ 代表第 $i$ 个商品的原价，$b[i]$ 代表折扣价