使用“成本"限制获取给定数组的所有子集 [英] Get all subset sof given array with 'cost' restiction

问题描述

我有一组类型元素和每种类型的价格

var array = new []{new Elem(0, Types.LowCost),新元素(1，类型.MediumCost)，new Elem(2, Types.MediumCost),新元素(3，Types.HightCost)，}

和价格:LowCost - 3，MediumCost - 5，HightCost - 9

您将如何找到具有限制所有元素的成本总和不超过限制"的元素的所有可能的唯一组合?

例如对于 MaxCost = 13 我期望

Elem(0)//成本 3元素(1)//5元素(2)//5元素(3)//9Elem(0), Elem(1)//成本3+5=8Elem(0), Elem(2)//3+5=8Elem(0), Elem(3)//3+9=12元素(1), 元素(2)//5+5 = 10Elem(0), Elem(1), Elem(2)//花费 13

解决方案

给定成本字典:

public Dictionary成本 = 新字典<类型，整数>(){{ Types.LowCost, 3 },{ Types.MediumCost, 5 },{ Types.HightCost, 9 },};

我可以这样做:

var 查询 =从 Enumerable.Range(0, 1 << array.Length).Skip(1) 中的 n让组合 = array.Where((x, i) => ((n >> i) & 1) == 1).ToArray()let cost = combine.Select(x => cost[x.Type]).Sum()其中成本 <= 13选择 String.Join(", ",combination.Select(x => x.Id));

这给了我:

<前>010, 120, 21、20, 1, 230, 3

I have a set of typed elements and price for each type

var array = new [] 
    {
        new Elem(0, Types.LowCost),
        new Elem(1, Types.MediumCost),
        new Elem(2, Types.MediumCost),
        new Elem(3, Types.HightCost),
    }

And prices: LowCost - 3, MediumCost - 5, HightCost - 9

How would you find all possible unique combinations of elements with restriction "sum of costs for all elements doesn't exceed a restriction"?

For example for MaxCost = 13 I expect

Elem(0)   //cost 3
Elem(1)   //     5
Elem(2)   //     5
Elem(3)   //     9
Elem(0), Elem(1)  //cost 3+5=8
Elem(0), Elem(2)  //     3+5=8
Elem(0), Elem(3)  //     3+9=12
Elem(1), Elem(2)  //     5+5 = 10
Elem(0), Elem(1), Elem(2) // cost 13

解决方案

Given a dictionary of costs:

public Dictionary<Types, int> costs = new Dictionary<Types, int>()
{
    { Types.LowCost, 3 },
    { Types.MediumCost, 5 },
    { Types.HightCost, 9 },
};

I can do this:

var query =
    from n in Enumerable.Range(0, 1 << array.Length).Skip(1)
    let combination = array.Where((x, i) => ((n >> i) & 1) == 1).ToArray()
    let cost = combination.Select(x => costs[x.Type]).Sum()
    where cost <= 13
    select String.Join(", ", combination.Select(x => x.Id));

That gives me:

0 
1 
0, 1 
2 
0, 2 
1, 2 
0, 1, 2 
3 
0, 3 

这篇关于使用“成本"限制获取给定数组的所有子集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！