CODEWITHSUNDEEP
matlabcombinations
smaen
smaen

Reputation: 1

Finding permutations under a set of linear constraints

I have two variables A and B, which both are 1x250 doubles. Variables A and B are related to one another. In other words, A(1) and B(1) are a pair (cause and effect).

A = [100, 1000, 254, 21,.....]

B = [-30, -100, -1254, -821,.....]

The problem is to find combinations in A that can meet two conditions below

  1. sums of any combinations in A should be <= 500
  2. At the same time, sum of corresponding value in B should be less than -5000

I tried to use nchoosek, but it really exploded after a few iterations due to the size of my variables.

Upvotes: 0

Views: 82

Answers (1)

MartinYakuza
MartinYakuza

Reputation: 135

What you said is pretty much impossible to do in terms of time complexity. If you need to check every combination in set of size of 250, you will need at least 2^250 operations, so that's order of magnitude of 10^75.

Unless you have some data about the values of the set, which lets you skip most of the combinations, or you limit yourself to combinations of 2 or 3, it's impossible to be done in sensible time.

Upvotes: 1

Related Questions