软件基础实践 | 最少费用购物（动态规划法）

1.问题描述：
商店中每种商品都有标价。例如，一朵花的价格是 2 元，一个花瓶的价格是 5 元。为了 吸引顾客，商店提供了一组优惠商品价。优惠商品是把一种或多种商品分成一组，并降价销 售。例如，3 朵花的价格不是 6 元而是 5 元，2 个花瓶加 1 朵花的优惠价是 10 元。试设计一 算法，计算出某一顾客所购商品应付的最少费用。

2.算法设计：
对于给定欲购商品的价格和数量，以及优惠商品价，计算所购商品应付的最少费用。
数据输入：

1. 提供欲购商品数据。第 1 行中有 1 个整数 B（0≤B≤5），表示所购商品种类数。接下来的 B 行，每行有 3 个数 C，K 和 P。C 表示商品的编码（每种商品有唯一编码），1≤C≤999。 K 表示购买该种商品总数，1≤K≤5。P是该种商品的正常单价（每件商品的价格），1≤P≤999。请注意，一次最多购买 5×5=25 件商品。
2. 提供优惠商品价数据。第 1 行中有 1 个整数 S（0≤S≤99），表示共有 S 种优惠商品组合。接下来的 S 行，每行的第 1 个数描述优惠商品组合中商品的种类数 j。接着是 j 个数字对（C，K），其中 C 是商品编码，1≤C≤999。K 表示该种商品在此组合中的数量，1≤K≤5。每行最后 1 个数字 P（1≤P≤9999）表示此商品组合的优惠价。
   数据输出：输出计算出的所购商品应付的最少费用。
   例：
   输入： 2 2
   7 3 2 1 7 3 5
   8 2 5 2 7 1 8 2 10
   输出： 14

文章知识点与官方知识档案匹配，可进一步学习相关知识算法技能树首页概览34070 人正在系统学习中

来源：Thorold’s Deer