商店购物

同样是在java坛做了一道作业——商品购物问题：
某商店中每种商品都有一个价格。例如，一朵花的价格是2 ICU(ICU 是信息学竞赛的货币的单位）;一个花瓶的价格是5 ICU。为了吸引更多的顾 客，商店提供了特殊优惠价。特殊优惠商品是把一种或几种商品分成一组。并降价销售。例如:3朵花的价格不是6而是5 ICU ;2个花瓶加1朵花是 10 ICU不是12 ICU。
编一个程序，计算某个顾客所购商品应付的费用。 要充分利用优惠价以使顾客付款最小。请注意，你不能变更顾客所购商品的种类及数量， 即使增加某些商品会 使付款总数减小也不允许你作出任何变更。假定各种商品价格用优惠价如上所述， 并且某顾客购买物品为:3朵花和2个花瓶。那么顾客应付款为14 ICU因 为:
1朵花加2个花瓶: 优惠价:10 ICU
2朵花 正常价: 4 ICU
输入数据
用两个文件表示输入数据。第一个文件INPUT．TXT描述顾客所购物品（放在购物筐中）;第二个文件描述商店提供的优惠商品及价格（文件名为OFF ER．TXT）。 两个文件中都只用整数。
第一个文件INPUT．TXT的格式为:第一行是一个数字B（0≤B≤5），表示所购商品种类数。下面共B行，每行中含3个数C，K，P。 C 代表商品 的编码（每种商品有一个唯一的编码），1≤C≤999。K代表该种商品购买总数，1≤K≤5。P 是该种商品的正常单价（每件商品的价格）， 1≤P≤999。请注意，购物筐中最多可放5*5＝25件商品。
第二个文件OFFER．TXT的格式为:第一行是一个数字S（0≤S≤9 9），表示共有S 种优惠。下面共S行，每一行描述一种优惠商品的组合中商品的 种类。下面接着是几个数字对（C，K），其中C代表商品编码，1≤C≤9 99。K代表该种商品在此组合中的数量，1≤K≤5。本行最后一个数字P （1≤ P≤9999）代表此商品组合的优惠价。当然， 优惠价要低于该组合中商品正常价之总和。
输出数据
在输出文件OUTPUT．TXT中写 一个数字（占一行）， 该数字表示顾客所购商品（输入文件指明所购商品）应付的最低货款。
输入/输出数据举例 （原例不是下面这个，下面这个是我用来测试用的）：
INPUT.TXT:
4
1 3 2
2 2 5
3 10 6
4 3 20
OFFER.TXT:
5
1 2 3
1 1 2 2 8
2 1 3 4 25
3 3 4 2 50
1 1 3 2 4 1 28

简析：
算法： 动态规划
数据结构： 字符串
题型： II 型
难度： 4 分
编程时间： 4分钟
简述： 本题竞赛时有一个很长的文件测试数据，用动态规划可较快的出答
案。 

我做这题的时候，没有仔细看上面的简析。而且对“动态规划 ”概念也不清楚，等这题做完，我才发现虽然我可以简单的得出结果，但是效率上不是最佳的，还需要好好学习一下。



import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.LineNumberReader;
import java.util.HashMap;
import java.util.Stack;

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 ...{
      test.init("INPUT.TXT", "OFFER.TXT");
      System.out.println(test.getMinPrice());
    } catch (NumberFormatException e) ...{
      e.printStackTrace();
    } catch (FileNotFoundException e) ...{
      e.printStackTrace();
    } catch (IOException e) ...{
      e.printStackTrace();
    }
  }

  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 = input.readLine();
      int lines = Integer.parseInt(str);
      int price = 0;
      for (int i = 0; i  < lines; i++) ...{
        str = input.readLine();
        String[] strs = str.split(" ");
        mapQuantity.put(Integer.parseInt(strs[0]), Integer
            .parseInt(strs[1]));
        mapPrice.put(Integer.parseInt(strs[0]), Integer
            .parseInt(strs[2]));
        price += Integer.parseInt(strs[1]) * Integer.parseInt(strs[2]);
      }
      mapQuantity.put(STR_PRICE, price);
      minPrice = price;
    } finally ...{
      if (input != null)
        try ...{
          input.close();
        } catch (IOException e) ...{
          e.printStackTrace();
        }
    }

    try ...{
      input = new LineNumberReader(new InputStreamReader(
          new FileInputStream(strOffer)));
      String str = input.readLine();
      int lines = Integer.parseInt(str);
      offers = new Offer[lines];
      for (int i = 0; i  < lines; i++) ...{
        offers[i] = new Offer();
        str = input.readLine();
        String[] strs = str.split(" ");

        int intOfferItems = strs.length / 2;
        offers[i].offerItems = new OfferItem[intOfferItems];
        int old_price = 0;
        for (int j = 0; j  < intOfferItems; j++) ...{
          offers[i].offerItems[j] = new OfferItem();
          offers[i].offerItems[j].id = Integer.parseInt(strs[j * 2]);
          offers[i].offerItems[j].count = Integer
              .parseInt(strs[j * 2 + 1]);
          old_price += offers[i].offerItems[j].count
              * ((Integer) mapPrice
                  .get(offers[i].offerItems[j].id))
                  .intValue();
        }
        offers[i].old_price = old_price;
        offers[i].new_price = Integer.parseInt(strs[strs.length - 1]);

      }
    } finally ...{
      if (input != null)
        try ...{
          input.close();
        } catch (IOException e) ...{
          e.printStackTrace();
        }
    }

  }

  public int getMinPrice() ...{
    procMinPrice(mapQuantity);
    return minPrice;
  }

  public void procMinPrice(HashMap mapQuantity) ...{
    boolean flg = true;
    for (int i = 0; i  < offers.length; i++) ...{
      HashMap hashMap = getQuantityFromOffer(mapQuantity, i);
      if (hashMap == null)
        continue;
      flg = false;
      stackOffer.push(i);
      procMinPrice(hashMap);
    }

    if (flg) ...{
      if (minPrice > ((Integer) mapQuantity.get(STR_PRICE)).intValue())
        minPrice = ((Integer) mapQuantity.get(STR_PRICE)).intValue();
    }
    if(stackOffer.size()>0)
      stackOffer.pop();
  }

  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) hashMap.get(STR_PRICE)).intValue();

    for (int i = 0; i  < offers[iOffer].offerItems.length; i++) ...{
      Integer integerCount = (Integer) hashMap
          .get(offers[iOffer].offerItems[i].id);
      if (integerCount == null)
        return null;
      int count = integerCount.intValue();
      if (count > offers[iOffer].offerItems[i].count)
        hashMap.put(offers[iOffer].offerItems[i].id, count
            - offers[iOffer].offerItems[i].count);
      else if (count == offers[iOffer].offerItems[i].count)
        hashMap.remove(offers[iOffer].offerItems[i].id);
      else
        return null;
    }
    hashMap.put(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;
  }
} 
执行结果是：114。

上面的程序的关键也就是procMinPrice函数，递归搜索所有可能的适用offer。
其他的都是周边的读文件和算价钱，没有什么好说的。

上面程序有个严重问题，就是会重复计算适用的offer：比方说第一个offer适用，然后检测到第二个offer也适用，这样算出一个总价；但是，先检测第二个offer再检测第一个offer的时候，又重复计算了一遍（其实这次检测也是不应该的）。

所以，题目说用动态规划是对的，我没有用。我用的是暴力搜索整个树的根到叶子的路径。效率不高，但是结果总算是出来了。

要改进的话，应该加个offer哈希表（注意不是集合，因为offer是可以重复的），以这个offer哈希表作为递归函数的参数传递（或者是全局变量）。

上面这个改进方法是不是最好，我现在心里也没有底，重新拿起《算法导论》，研究一下后再回头来判断一下，看看怎么改进。

• 上一个： 一个自动生成Hibernate ORM映射文件的工具函数

• 下一个： java文字转成图片显示