选择最小成本组合

Question

选择最小成本组合

3

我有不同餐厅的不同物品数据

    Rest    Item     Price
    ----------------------
    ABC     dosa      14
    ABC     idly      30
    ABC     idly+upma 25

    123     dosa      30
    123     idly      7
    123     upma      12

    XYZ     dosa      20
    XYZ     idly      12
    XYZ     upma      20
    XYZ     dosa+upma 30
    XYZ     dosa+idly+upma 40

现在我需要挑选一个餐厅，给我提供最好的“dosa+idly+upma”套餐。

从上面的例子可以看出：这将是餐厅“ABC”

我无法设计有效的解决方案，也不知道该如何做？有什么想法吗？

更新

这是我的对象长什么样子：

Class Rest{
  Map<String,Integer> menu; //item,price map
}

- RaceBase

dosa+idly+upma ABC，价格为39卢比，对吧？ - Kick

@amit，这是样本数据。希望它能够高效处理。数据上没有太多限制。 - RaceBase

1

那规模是多少呢？几十个？几百个？几千个？还是几百万个？如果只有几十个，不要太费心去优化它。但如果是数百万个，那就完全是另一回事了。 - amit

@LastFreeNickname，你能提供一些可行的代码/伪代码吗？我知道这将是指数级的，但我现在无从下手 :( - RaceBase

@Reddy，我在我的帖子中为你添加了一个伪代码草图。虽然它很丑... - LastFreeNickname

显示剩余5条评论

5个回答

1

尝试

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class Mult {
    /**
     * @param args
     */
    public static void main(String[] args) {
        Map<String,List<X>> xx = new HashMap<String,List<X>>();
        xx.put("ABC",new ArrayList<X>());
        xx.get("ABC").add(new X("", 0));
        xx.get("ABC").add(new X("dosa", 14));
        xx.get("ABC").add(new X("idly", 30));
        xx.get("ABC").add(new X("idly+upma", 25));


        xx.put("123",new ArrayList<X>());
        xx.get("123").add(new X("", 0));
        xx.get("123").add(new X("dosa", 30));
        xx.get("123").add(new X("idly", 7));
        xx.get("123").add(new X("upma", 12));


        xx.put("XYZ",new ArrayList<X>());
        xx.get("XYZ").add(new X("", 0));
        xx.get("XYZ").add(new X("dosa", 20));
        xx.get("XYZ").add(new X("idly", 12));
        xx.get("XYZ").add(new X("upma", 20));
        xx.get("XYZ").add(new X("dosa+upma", 30));
        xx.get("XYZ").add(new X("dosa+idly+upma", 40));

        String[] t = {
                "dosaidlyupma",
                "idlydosaupma",
                "upmaidlydosa",
                "dosaupmaidly",
                "upmadosaidly",
                "idlyupmadosa"};
        Set<String> targets = new HashSet<String>(Arrays.asList(t));

        Map<String,Integer> best = new HashMap<String,Integer>();

        for(String restaurant:xx.keySet()){
            best.put(restaurant, Integer.MAX_VALUE);
            String combo = null;
            for(X a:xx.get(restaurant)){
                int deal = a.price;
                combo = a.item;
                for(X b:xx.get(restaurant)){
                    deal = deal + b.price;
                    combo = combo + "+" + b.item;
                    for(X c:xx.get(restaurant)){
                        deal = deal + c.price;
                        combo = combo + "+" + c.item;
                        if (targets.contains(combo.replaceAll("\\+", ""))){
//                          System.out.println(restaurant+"\t"+combo.replaceAll("\\+", "")+"\t"+deal);
                            if (best.get(restaurant) > deal){
                                best.put(restaurant, deal);                 
                            }
                        }
                    }
                }
            }
        }

        System.out.println(best);
    }

}

将为您提供

{XYZ=40，ABC=39，123=49}

这是旧的暴力方法。

虽然不是最好的方法，但对于这个小集合来说，它很有效。

- Leo

1

一种可能的贪心算法草图如下：

遍历所有一元报价（例如，dosa、idly或upma），找到每个最小值。
遍历所有二元（例如，idly+upma）/三元... 报价，比较是否比一元报价更便宜，如果是，则替换。

您仍需要编写报价解析代码，但这不应该很难。此算法将找到好的解决方案，但不一定是最佳解决方案，并且可能适用于非常小的样本。

实际上，您的问题与背包或TSP问题相比，它们是NP完全问题，因此只能在指数时间内解决。如果您想要解决方案，请考虑阅读大量论文并编写更多代码。那是计算机科学的圣杯。;-)

更新：根据TO的要求，这里有一些指数级伪代码草图：

foreach restaurant
    create a list of all possible combinations of the offers // here's the exp!
    filter those combinations that hold more/less than 1 dosy/idly/umpa
    select minimum of the remaining ones

评论：这真的很丑，呸！:-(

- LastFreeNickname

肯定有比每次查询都暴力搜索整个数据库更高效的解决方案... - amit

@LastFreeNickname，由于我不考虑大规模数据，并且我知道对于长数据它是NP问题或者不能处理大数据。对于这个简单的数据，假设我没有超过5家餐厅，每家餐厅不超过10个项目。 - RaceBase

@Reddy 那么你唯一的可能性就是像上面解释的那样进行暴力破解，并希望你的数据永远不会变得很大。 :-) 你可以考虑比我更肮脏的方法来保持算法简单。 - LastFreeNickname

0

首先，您需要创建所有可能的三个项目组合，对应不同的餐厅，例如：

XYZ     dosa+idly+upma 52
XYZ     dosa+upma+idly 42
XYZ     dosa+idly+upma 40

对于所有餐厅，情况与上述案例相同。

然后按价格排序，让最低价格的餐厅获胜。

- Kick

假设3只是一个例子，你可能在餐厅里有更多的物品，而你只会要求其中的一部分 - 这种方法需要为每个餐厅创建2^n不同的集合，其中n是元素的总数，如果你想在预处理中完成它。 - amit

@amit 根据要求，我已经提供了答案。 - Kick

需求并没有说要3个项目，只是例子中有3个。 - amit

我怎么知道它的例子或要求？如果您想扩展项目，那么您需要使用相同的逻辑。 - Kick

0

计算可能的价格组合：遍历映射并解析字符串。存储每个价格组合。
筛选掉更贵的价格。
比较每个餐厅剩余的价格，返回最便宜的餐厅。

您还可以执行一些检查以最小化迭代，例如：

如果 idly 大于 idly+umpa，则不计算涉及 idly 的任何组合。

- Someone

一开始我也这么想，但是一旦在这种方法中包含了 >=1 的商品报价，比较的顺序就会改变结果。比如说，idly+upma 可能会阻止 dosa+idly 替换，反之亦然。请参阅我的帖子以获取更详细的解释。 - LastFreeNickname

@LastFreeNickname，抱歉我不太明白你的意思。你是指第二步吗？ - Someone

如果我理解帖子的开启者，任务也包括将min_upma和min_idly替换为min_upmaidly。这部分缺失了。 - LastFreeNickname

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- amit · Accepted Answer

这个问题是NP-Hard的。我将展示从Set Cover Problem进行的约简。

集合覆盖问题（SCP）：
给定元素的宇宙U（例如U={dosa,idly,upma}）和U的子集的集合S（例如S={{dosa}, {idly,upma}, {upma}}），找出最小数量的S子集，使它们的并等于U。

约简：
给定一个具有U和S的集合覆盖问题，创建一个只有一个餐厅的问题实例，使得S中每个项目的价格为1。

现在，假设您的问题有最优解-最小价格可能是覆盖“宇宙”所需的最小子集数。
如果给定集合覆盖问题的最优解，则所需集合的数量是子集的最小价格。 结论:
由于我们已经看到有效地解决此问题将有效地解决SCP，因此我们可以得出结论，该问题是NP难的，因此没有已知的多项式解决方案（并且大多数人认为不存在这样的解决方案）。

替代方案是使用启发式解决方案或暴力解决方案（仅搜索所有可能性，在指数时间内）。