蓝桥杯算法提高促销购物(动态规划+完全背包)_牛客博客

admin 三生目录 2024-04-12 46浏览 0

　　/问题描述

　　张超来到了超市购物。

　　每个物品都有价格，正好赶上商店推出促销方案。就是把许多东西一起买更便宜（保证优惠方案一定比原价便宜）。物品要买正好的个数，而且不能为了便宜而买不需要的物品。

　　张超拿到了优惠方案，和需要购买的物品清单，当然想求出最小的花费。他是信息学选手，自然地想到写个程序解决问题。

　　输入格式

　　第一行促销物品的种类数（0 <= s <= 99）。

　　第二行…第s+1 行每一行都用几个整数来表示一种促销方式。

蓝桥杯算法提高促销购物(动态规划+完全背包)_牛客博客

　　第一个整数 n （1 <= n <= 5），表示这种优惠方式由 n 种商品组成。

　　后面 n 对整数 c 和 k 表示 k （1 <= k <= 5）个编号为 c （1 <= c <= 999）的商品共同构成这种方案。

　　最后的整数 p 表示这种优惠的优惠价（1 <= p <= 9999）。也就是把当前的方案中的物品全买需要的价格。

　　第 s+2 行这行一个整数b （0 <= b <= 5），表示需要购买 b 种不同的商品。

　　第 s+3 行…第 s+b+2 行这 b 行中的每一行包括三个整数：c ，k ，和 p 。

　　C 表示唯一的商品编号（1 <= c <= 999），

蓝桥杯算法提高促销购物(动态规划+完全背包)_牛客博客

　　k 表示需要购买的 c 商品的数量（1 <= k <= 5）。

　　p 表示 c 商品的原价（1 <= p <= 999）。

　　最多购买 55=25 个商品。

　　输出格式

　　一个整数ans，表示需要花的最小费用

　　样例输入

　　2

　　1 7 3 5

　　2 7 1 8 2 10

　　2

蓝桥杯算法提高促销购物(动态规划+完全背包)_牛客博客

　　7 3 2

　　8 2 5

　　样例输出

　　14

　　思路：动态规划完全背包变形

　　*/

转载请注明：CQ9电子·(中国)唯一官方网站 » 三生目录 » 蓝桥杯算法提高促销购物(动态规划+完全背包)_牛客博客

版权声明

本文仅代表作者观点，不代表B5编程立场。
本文系作者授权发表，未经许可，不得转载。