c*******n
发帖数: 112 | 1 You are given a list of items / combo_items with their price list.
And you are given list of items to buy.
Now you are asked to find which combination to buy so that it costs you
minimum.
It doesnt matter if you are getting some extra items if it costs less.
Sr.No Price | Items/Combo_Items
1. 5 | Burger
2. 4 | French_Frice
3. 8 | Coldrink
4. 12 | Burger, French_Frice, Coldrink
5. 14 | Burger, Coldrink
Input Items to Buy:
Coldrink
Output(Sr.No)
3
Input Items to Buy:
Burger Coldrink
Output(Sr.No)
4
Input Items to Buy:
Burger French_Frice
Output(Sr.No)
1,2 | h*******e
发帖数: 1377 | | v***o
发帖数: 287 | 3 最笨，也最快的办法：
每个combo items 产生一个 set, 然后，用一个pair 或 class 存(set, price number
)， 最后，用个array 穿以来。
对每个input search 那个array, 找出最便宜的price number.
这个题更像考data structure design.
【在 c*******n 的大作中提到】
: You are given a list of items / combo_items with their price list.
: And you are given list of items to buy.
: Now you are asked to find which combination to buy so that it costs you
: minimum.
: It doesnt matter if you are getting some extra items if it costs less.
: Sr.No Price | Items/Combo_Items
: 1. 5 | Burger
: 2. 4 | French_Frice
: 3. 8 | Coldrink
: 4. 12 | Burger, French_Frice, Coldrink
| h*******e
发帖数: 1377 | 4 item 是多维的，你的array里每个元素的个数也是互相依赖的， 要bfs才行，做过类
似的题目。
如果有数目限制的话可以状态压缩dp，如果维数很大，而且combo每个可能取的也超
多的话只能dfs，， 。
number
【在 v***o 的大作中提到】
: 最笨，也最快的办法：
: 每个combo items 产生一个 set, 然后，用一个pair 或 class 存(set, price number
: )， 最后，用个array 穿以来。
: 对每个input search 那个array, 找出最便宜的price number.
: 这个题更像考data structure design.
| Q*****a
发帖数: 33 | 5 几个优化方案：
对输入价格列表按物品个数排序，长的输入先计算能否用短的输入以更低成本表示，若
是则将其从价格列表中删除，这样可以减少价格列表数目，优化搜索
匹配时对价格列表按长到短搜索，到长度为1列表时直接计算，不用搜索了
备忘录记录中间搜索结果（内存会否爆棚)
简单贪心法行不通（也许有更好的贪心法本人没想到）
(i2,I4,I6,i8,i10): 5
(i1, i2):2
(i3, i4):2
(i5, i6):2
(i7, i8):2
(i9, i10):2
i1…i10:2
对于此价格列表，(i1,i2,i3,i4,i6,,i8,i10)最优解为[(i2,i4,i6,i8,i10), (i1), (
i3)]=9,而(i1,i2,i3,i4,i5,i6,i8,i10)最优解为[(i1,i2),(i3,i4),(i5,i6),i8,i10]=
10 | a*****y
发帖数: 22 | 6 我有一个想法：
先建立map存储价格：(设商品用id表示)
struct ItemPrice {
std::vector items;
int price;
};
std::map > item_prices_;
表示将某个商品映射到所有包含该商品的组合或单件商品的价格
所求：
std::map< std::set, int > min_price_;
int FindMinPrice(const std::set& items, const std::set& used_items
) {
std::set target;
// target = items - used_items
if (target.empty()) {
return 0;
}
if (min_prices_.count(itesms) > 0) {
return ...;
}
int min = 0x7FFFFFF;
// get the first item in target, let it be a
for (int i = 0; i < item_prices_[a].size(); ++i) {
int curr = item_prices_[a][i].price;
// std::set new_used_items = used_items + other items in item_
prices_[a].items
if (curr + FindMinPrice(items, new_used_items)) {
min = ...;
}
}
min_price[items] = min;
return min;
} | r***s
发帖数: 737 | 7 你的这个map就是一个reverse index，对么？
另外我觉得你的code不对，对于每一个商品或组合，都要两次调用递归函数
一次假设取当前商品或组合，一次不取
【在 a*****y 的大作中提到】
: 我有一个想法：
: 先建立map存储价格：(设商品用id表示)
: struct ItemPrice {
: std::vector items;
: int price;
: };
: std::map > item_prices_;
: 表示将某个商品映射到所有包含该商品的组合或单件商品的价格
: 所求：
: std::map< std::set, int > min_price_;
| n*******1
发帖数: 145 | 8 这题有问题吧 5号根本没有存在意义啊 一块买比单买还贵 就用4号匹配 剩下的单买不
就行了 |
|
