|
同样是在java坛做了一道作业——商品购物问题 某商店中每种商品都有一个价格例如一朵花的价格是 ICU(ICU 是信息学竞赛的货币的单位）;一个花瓶的价格是 ICU为了吸引更多的顾 客商店提供了特殊优惠价特殊优惠商品是把一种或几种商品分成一组并降价销售例如:朵花的价格不是而是 ICU ;个花瓶加朵花是 ICU不是 ICU 编一个程序计算某个顾客所购商品应付的费用 要充分利用优惠价以使顾客付款最小请注意你不能变更顾客所购商品的种类及数量 即使增加某些商品会 使付款总数减小也不允许你作出任何变更假定各种商品价格用优惠价如上所述 并且某顾客购买物品为:朵花和个花瓶那么顾客应付款为 ICU因 为: 朵花加个花瓶: 优惠价: ICU 朵花 正常价: ICU 输入数据 用两个文件表示输入数据第一个文件INPUT．TXT描述顾客所购物品（放在购物筐中）;第二个文件描述商店提供的优惠商品及价格（文件名为OFF ER．TXT） 两个文件中都只用整数 第一个文件INPUT．TXT的格式为:第一行是一个数字B（≤B≤）表示所购商品种类数下面共B行每行中含个数CKP C 代表商品 的编码（每种商品有一个唯一的编码）≤C≤K代表该种商品购买总数≤K≤P 是该种商品的正常单价（每件商品的价格） ≤P≤请注意购物筐中最多可放*＝件商品 第二个文件OFFER．TXT的格式为:第一行是一个数字S（≤S≤ ）表示共有S 种优惠下面共S行每一行描述一种优惠商品的组合中商品的 种类下面接着是几个数字对（CK）其中C代表商品编码≤C≤ K代表该种商品在此组合中的数量≤K≤本行最后一个数字P （≤ P≤）代表此商品组合的优惠价当然 优惠价要低于该组合中商品正常价之总和 输出数据 在输出文件OUTPUT．TXT中写 一个数字（占一行） 该数字表示顾客所购商品（输入文件指明所购商品）应付的最低货款 输入/输出数据举例 （原例不是下面这个下面这个是我用来测试用的） INPUTTXT: OFFERTXT: 简析 算法 动态规划 数据结构 字符串 题型 II 型 难度 分 编程时间 分钟 简述 本题竞赛时有一个很长的文件测试数据用动态规划可较快的出答 案 我做这题的时候没有仔细看上面的简析而且对动态规划 概念也不清楚等这题做完我才发现虽然我可以简单的得出结果但是效率上不是最佳的还需要好好学习一下 import javaioFileInputStream; import javaioFileNotFoundException; import javaioIOException; import javaioInputStreamReader; import javaioLineNumberReader; import javautilHashMap; import javautilStack; public class Test { final static String STR_PRICE = price; HashMap mapQuantity; HashMap mapPrice; Offer[] offers; Stack stackOffer; int minPrice; public static void main(String[] strsArg) { Test test = new Test(); try { testinit(INPUTTXT OFFERTXT); Systemoutprintln(testgetMinPrice()); } catch (NumberFormatException e) { eprintStackTrace(); } catch (FileNotFoundException e) { eprintStackTrace(); } catch (IOException e) { eprintStackTrace(); } } public Test() { mapQuantity = new HashMap(); mapPrice = new HashMap(); stackOffer = new Stack(); } public void init(String strInput String strOffer) throws FileNotFoundException IOException NumberFormatException { LineNumberReader input = null; try { input = new LineNumberReader(new InputStreamReader( new FileInputStream(strInput))); String str = inputreadLine(); int lines = IntegerparseInt(str); int price = ; for (int i = ; i < lines; i++) { str = inputreadLine(); String[] strs = strsplit( ); mapQuantityput(IntegerparseInt(strs[]) Integer parseInt(strs[])); mapPriceput(IntegerparseInt(strs[]) Integer parseInt(strs[])); price += IntegerparseInt(strs[]) * IntegerparseInt(strs[]); } mapQuantityput(STR_PRICE price); minPrice = price; } finally { if (input != null) try { inputclose(); } catch (IOException e) { eprintStackTrace(); } } try { input = new LineNumberReader(new InputStreamReader( new FileInputStream(strOffer))); String str = inputreadLine(); int lines = IntegerparseInt(str); offers = new Offer[lines]; for (int i = ; i < lines; i++) { offers[i] = new Offer(); str = inputreadLine(); String[] strs = strsplit( ); int intOfferItems = strslength / ; offers[i]offerItems = new OfferItem[intOfferItems]; int old_price = ; for (int j = ; j < intOfferItems; j++) { offers[i]offerItems[j] = new OfferItem(); offers[i]offerItems[j]id = IntegerparseInt(strs[j * ]); offers[i]offerItems[unt = Integer parseInt(strs[j * + ]); old_price += offers[i]offerItems[unt * ((Integer) mapPrice get(offers[i]offerItems[j]id)) intValue(); } offers[i]old_price = old_price; offers[i]new_price = IntegerparseInt(strs[strslength ]); } } finally { if (input != null) try { inputclose(); } catch (IOException e) { eprintStackTrace(); } } } public int getMinPrice() { procMinPrice(mapQuantity); return minPrice; } public void procMinPrice(HashMap mapQuantity) { boolean flg = true; for (int i = ; i < offerslength; i++) { HashMap hashMap = getQuantityFromOffer(mapQuantity i); if (hashMap == null) continue; flg = false; stackOfferpush(i); procMinPrice(hashMap); } if (flg) { if (minPrice > ((Integer) mapQuantityget(STR_PRICE))intValue()) minPrice = ((Integer) mapQuantityget(STR_PRICE))intValue(); } if(stackOffersize()>) stackOfferpop(); } private HashMap getQuantityFromOffer(HashMap mapQuantity int iOffer) { if (offers[iOffer]new_price >= offers[iOffer]old_price) return null; HashMap hashMap = new HashMap(mapQuantity); int price = ((Integer) hashMapget(STR_PRICE))intValue(); for (int i = ; i < offers[iOffer]offerItemslength; i++) { Integer integerCount = (Integer) hashMap get(offers[iOffer]offerItems[i]id); if (integerCount == null) return null; int count = integerCountintValue(); if (count > offers[iOffer]offerItems[unt) hashMapput(offers[iOffer]offerItems[i]id count offers[iOffer]offerItems[unt); else if (count == offers[iOffer]offerItems[unt) hashMapremove(offers[iOffer]offerItems[i]id); else return null; } hashMapput(STR_PRICE price offers[iOffer]old_price + offers[iOffer]new_price); return hashMap; } class Offer { OfferItem[] offerItems; int new_price; int old_price; } class OfferItem { int id; int count; } } 执行结果是 上面的程序的关键也就是procMinPrice函数递归搜索所有可能的适用offer 其他的都是周边的读文件和算价钱没有什么好说的 上面程序有个严重问题就是会重复计算适用的offer比方说第一个offer适用然后检测到第二个offer也适用这样算出一个总价但是先检测第二个offer再检测第一个offer的时候又重复计算了一遍（其实这次检测也是不应该的） 所以题目说用动态规划是对的我没有用我用的是暴力搜索整个树的根到叶子的路径效率不高但是结果总算是出来了 要改进的话应该加个offer哈希表（注意不是集合因为offer是可以重复的）以这个offer哈希表作为递归函数的参数传递（或者是全局变量） 上面这个改进方法是不是最好我现在心里也没有底重新拿起《算法导论》研究一下后再回头来判断一下看看怎么改进 |
