CODEWITHSUNDEEP
c#algorithm
darkhac
darkhac

Reputation: 589

Get all subset sof given array with 'cost' restiction

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

Upvotes: 0

Views: 37

Answers (1)

Enigmativity
Enigmativity

Reputation: 117064

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

Upvotes: 3

Related Questions