商店購物

　　同樣是在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哈希表作為遞歸函數的參數傳遞（或者是全局變量）

　　上面這個改進方法是不是最好我現在心裡也沒有底重新拿起《算法導論》研究一下後再回頭來判斷一下看看怎麼改進

From:http://tw.wingwit.com/Article/program/Java/hx/201311/26607.html