m********c
发帖数: 105 | 1 我在看bloomreach的opening的时候，看到这个puzzle，题目是wine testing。下面是
描述，链接在这个http://bloomreach.com/puzzles/
A large group of friends from the town of Nocillis visit the vineyards of
Apan to taste wines. The vineyards produce many fine wines and the friends
decide to buy as many as 3 bottles of wine each if they are available to
purchase. Unfortunately, the vineyards of Apan have a peculiar restriction
that they can not sell more than one bottle of the same wine. So the
vineyards come up with the following scheme: They ask each person to write
down a list of up to 10 wines that they enjoyed and would be happy buying.
With this information, please help the vineyards maximize the number of
wines that they can sell to the group of friends.
简单点说就是有很多的朋友想买酒，但是每种酒最多只能卖一次，一个人最多可以买三
种酒。题目给了每个人想买的酒的id，每个人最多想买10种。根据这个信息，问酒庄如
何可以卖出最多的酒。
我昨天想了想，觉得这个题目类似set cover或者set packing problem。解法的话就是
用greedy。但是总觉得不太好，不知道大家有没有更好的思路。 |
k******4
发帖数: 94 | 2 Max fllow 算法？建立有向图。一边是人，一边是酒，人和酒之间加link，同时添加两
个辅助节点s d，s到每个人加link，每瓶酒到d之间加link，然后计算两个辅助节点s d
之间的max。flow |
k******4
发帖数: 94 | 3 补充下， s到人之间link weight为3，其它为1。 |
m********c
发帖数: 105 | 4 max flow是个思路。但是我想了想，max flow里每一个edge有不同capacity，是要计算
在符合capacity的情况下最大的flow是多少。但是这个情况里，人和酒之间没有
capacity，而且是要计算能有多少酒卖出去，也就是能有多少flow经过酒的node。这也
和max flow不一样。
d
【在 k******4 的大作中提到】
: Max fllow 算法？建立有向图。一边是人，一边是酒，人和酒之间加link，同时添加两
: 个辅助节点s d，s到每个人加link，每瓶酒到d之间加link，然后计算两个辅助节点s d
: 之间的max。flow
|
k******4
发帖数: 94 | |
m********c
发帖数: 105 | 6 不明白，我上wikipedia上看了看max flow，是从source到sink之间，所有node之间的
max flow。但是这个里面，人和人之间酒和酒之间不能有flow吧？
【在 k******4 的大作中提到】
: 人和酒的capacity为1？
|
k******4
发帖数: 94 | 7 我没说清楚，人和人之间还有酒和酒之间没有link，人和酒之间link的capacity为1，
酒和d之间也是1，但是s和人之间是3 |
l*n
发帖数: 529 | 8 这个办法好。
【在 k******4 的大作中提到】
: 我没说清楚，人和人之间还有酒和酒之间没有link，人和酒之间link的capacity为1，
: 酒和d之间也是1，但是s和人之间是3
|
b***e
发帖数: 1419 | 9 这个是典型的匈牙利算法。放狗搜一下就知道了。
【在 m********c 的大作中提到】
: 我在看bloomreach的opening的时候，看到这个puzzle，题目是wine testing。下面是
: 描述，链接在这个http://bloomreach.com/puzzles/
: A large group of friends from the town of Nocillis visit the vineyards of
: Apan to taste wines. The vineyards produce many fine wines and the friends
: decide to buy as many as 3 bottles of wine each if they are available to
: purchase. Unfortunately, the vineyards of Apan have a peculiar restriction
: that they can not sell more than one bottle of the same wine. So the
: vineyards come up with the following scheme: They ask each person to write
: down a list of up to 10 wines that they enjoyed and would be happy buying.
: With this information, please help the vineyards maximize the number of
|
s*****n
发帖数: 994 | 10 一共有多少种酒？
【在 m********c 的大作中提到】
: 我在看bloomreach的opening的时候，看到这个puzzle，题目是wine testing。下面是
: 描述，链接在这个http://bloomreach.com/puzzles/
: A large group of friends from the town of Nocillis visit the vineyards of
: Apan to taste wines. The vineyards produce many fine wines and the friends
: decide to buy as many as 3 bottles of wine each if they are available to
: purchase. Unfortunately, the vineyards of Apan have a peculiar restriction
: that they can not sell more than one bottle of the same wine. So the
: vineyards come up with the following scheme: They ask each person to write
: down a list of up to 10 wines that they enjoyed and would be happy buying.
: With this information, please help the vineyards maximize the number of
|
k******4
发帖数: 94 | 11 找最大匹配的话，还要剔除那些有人买了大于三瓶酒的情况。
【在 b***e 的大作中提到】
: 这个是典型的匈牙利算法。放狗搜一下就知道了。
|
m********c
发帖数: 105 | 12 嗯，我试试
【在 k******4 的大作中提到】
: 我没说清楚，人和人之间还有酒和酒之间没有link，人和酒之间link的capacity为1，
: 酒和d之间也是1，但是s和人之间是3
|
b***e
发帖数: 1419 | 13 每个人3个点就行了。
【在 k******4 的大作中提到】
: 找最大匹配的话，还要剔除那些有人买了大于三瓶酒的情况。
|
k******4
发帖数: 94 | 14 说的对，我想错了。
每个人3个点就行了。
【在 b***e 的大作中提到】
: 每个人3个点就行了。
|
