商店购物
某商店中每种商品都有一个价格。例如,一朵花的价格是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 │ │ OFFER.TXT ││ OUTPUT.TXT│
├────────┤ ├────────────┤├────────┤
│ 2 │ │ 2 ││ 14 │
│ 7 3 2 │ │ 1 7 3 5 ││ │
│ 8 2 5 │ │ 2 7 1 8 2 10 ││ │
└────────┘ └────────────┘└────────┘
简析:
算法: 动态规划
数据结构: 字符串
题型: II 型
难度: 4 分
编程时间: 4分钟
简述: 本题竞赛时有一个很长的文件测试数据,用动态规划可较快的出答
案。 最好能给个注释!谢谢!
某商店中每种商品都有一个价格。例如,一朵花的价格是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 │ │ OFFER.TXT ││ OUTPUT.TXT│
├────────┤ ├────────────┤├────────┤
│ 2 │ │ 2 ││ 14 │
│ 7 3 2 │ │ 1 7 3 5 ││ │
│ 8 2 5 │ │ 2 7 1 8 2 10 ││ │
└────────┘ └────────────┘└────────┘
简析:
算法: 动态规划
数据结构: 字符串
题型: II 型
难度: 4 分
编程时间: 4分钟
简述: 本题竞赛时有一个很长的文件测试数据,用动态规划可较快的出答
案。 最好能给个注释!谢谢!
根据第二个文件OFFER.TXT的格第一行数字S,做一个S层的For循环,
1.按满足1层0,1,2,……n次的顺序处理,其余的部分进入下1层处理
2.第2层至第S层一次类推。
3.如果m还没有得出,把结果给m;如果m已有数,把比m小的结果赋值给m,否则跳过
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结果:
114
(如果想把适用了那些offer给记录下来,把下面程序的最小结果的stackOffer给记录下来,并输出就可以,我就不写了)
程序如下: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;
}
}
其他的都是周边的读文件和算价钱,没有什么好说的。上面程序有个严重问题,就是会重复计算适用的offer:比方说第一个offer适用,然后检测到第二个offer也适用,这样算出一个总价;但是,先检测第二个offer再检测第一个offer的时候,又重复计算了一遍(其实这次检测也是不应该的)。所以,题目说用动态规划是对的,我没有用。我用的是暴力搜索整个树的根到叶子的路径。效率不高,但是结果总算是出来了。要改进的话,应该加个offer哈希表(注意不是集合,因为offer是可以重复的),以这个offer哈希表作为递归函数的参数传递(或者是全局变量)。