最优算法-选择集的子集，使成本最小化。

Question

我有产品清单，需要编写一个算法来计算给客户一个最小的价格。

每一种产品都有自己的价格，并且有一组价格--几种产品的价格合在一起。

该算法将计算要选择哪一组才能获得最低价格。

例如，： 假设客户想购买产品c1，c2，c3，c4，价格是：c1=70美元，c2=70美元，c3=70美元，c4=70美元。 当组为：时： g1 = {c1，c2} = 120 $ g2 = {c3，c4} = 130 g3 = {c2，c3，c4} = 170 备选方案如下： 1.为每种产品分别支付70美元，=280美元 2.选择购买g1集团，g2= 250美元 3.选择分别购买g3 + product c1 =240美元 无论如何，可能还有更多的选择--在本例中，最便宜的价格是第三个选项，组g3+c1,240美元。

什么算法能解决这个问题？

检查所有可能的组组合，找出最低价格和使用哪组。

我确信这是一个熟悉的算法，在极客为极客中存在一个问题，我只是不知道如何设置它，它的著名名称是什么。

Answer 1

设置封面问题- GeeksforGeeks：

public static int minCostCollection(final Set<Integer> unv, final Set<Integer>[] sets,
        final Map<Set, Integer> costs, final List<Set> list, final int pos) {

    if (unv.size() == 0) {
        int cost = 0;
        for (final Set s : list) {
            cost = cost + costs.get(s);
        }
        return cost;
    }
    if (pos < 0) {
        return Integer.MAX_VALUE;
    }
    final Set<Integer> unvCopy = new HashSet<>(unv);
    final List<Set> list1 = new ArrayList<>(list);
    list.add(sets[pos]);
    for (final Integer elem : sets[pos]) {
        unv.remove(elem);
    }
    final int cost1 = minCostCollection(unv, sets, costs, list, pos - 1);
    final int cost2 = minCostCollection(unvCopy, sets, costs, list1, pos - 1);
    return Math.min(cost1, cost2);

}


public static void main(final String[] args) {
        final Set<Integer> unv = new HashSet<>();
        unv.add(1);
        unv.add(2);
        unv.add(3);
        unv.add(4);
        unv.add(5);
        final Set<Integer> s1 = new HashSet<>();
        s1.add(4);
        s1.add(1);
        s1.add(3);
        final Set<Integer> s2 = new HashSet<>();
        s2.add(2);
        s2.add(5);
        final Set<Integer> s3 = new HashSet<>();
        s3.add(1);
        s3.add(4);
        s3.add(3);
        s3.add(2);
        final Set sets[] = {s1, s2, s3};
        final Map<Set, Integer> costs = new HashMap<>();
        costs.put(s1, 5);
        costs.put(s2, 10);
        costs.put(s3, 30);
        System.out.println(minCostCollection(unv, sets, costs, new ArrayList<Set>(), sets.length - 1));
    }