商店中每种商品都有标價例如,一朵花的价格是 2 元一个花瓶的价格是 5 元。为了吸引顾客商店提供了一组优惠商品价。优惠商品是把一种或多种商品分成一組并降价销 售。例如3 朵花的价格不是 6 元而是 5 元。2 个花瓶加 1 朵花的优惠价是 10 元试设计一个算法,计算出某一顾客所购商品应付的最少費用
对于给定欲购商品的价格和数量,以及优惠商品价编程计算所购商品应付的最少费用。
由文件 input.txt 提供欲购商品数据文件的第 1 行中囿 1 个整数 B(0≤B≤5),表示所购商品种类数接下来的 B 行,每行有 3 个数 CK 和 P。C 表示商品的编码(每种商品有 唯一编码)1≤C≤999。K 表示购买该种商品总數1≤K≤5。P 是该种商品的正常单价(每件商品的价格)1≤P≤999。请注意一次最多可购买 5*5=25 件商品。
由文件 offer.txt 提供优惠商品价数据文件的第 1 行中囿 1 个整数 S(0≤S≤99),表示 共有 S 种优惠商品组合接下来的 S 行,每行的第一个数描述优惠商品组合中商品的种类数 j接着是 j 个数字对(C,K)其中 C 是商品编码,1≤C≤999K 表示该种商品在此组合中的数量,1≤K≤5每行最后一个数字 P(1≤ P≤9999)表示此商品组合的优惠价。
王晓东《计算机算法设计与汾析》(第3版)P95