0

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.

Adriaan
  • 17,741
  • 7
  • 42
  • 75
smaen
  • 1
  • 1
  • Combinations of A? i.e. you want something like `C=[A(12),A(100), A(234)]` ? You need to find all combinations? – Ander Biguri Nov 18 '22 at 14:51
  • If that is the case, you need to write your own code. Make first a loop that produces all possible combinations, and once found one, checks if the B condition is met. However, indeed, if you don't add extra constrains, or your data looks particularly good (e.g. the maximum length of combined A's is small) this will blow up badly. In any case, also start by sorting A and B w.r.t. A. It will make your job way easier. – Ander Biguri Nov 18 '22 at 14:54
  • Thanks Ander. To your question, YES I want something like C. It could also be something like C = [1,0,0,1..] can tell which combination of values can meet the conditions. Using nchoosek doesn't seem to work because it required too much. – smaen Nov 18 '22 at 15:05
  • 1
    The [knapsack problem](https://en.wikipedia.org/wiki/Knapsack_problem) might get you started. In this case your knapsack would have a capacity of 500 `A` and `-5000` B. There are good algorithms to solve this already. Don't try to brute force this, it's a classical optimisation problem. Brute forcing will take longer than possible, see [MartinYakuza's answer](https://stackoverflow.com/a/74491624/5211833). – Adriaan Nov 18 '22 at 15:15
  • If all values in `B` are negative, this reduces to a single Knapsack for `A<500`, because `B` will sum to more and more negative numbers. Did you mean `-5000 < B < 0` instead? – Adriaan Nov 18 '22 at 15:43
  • Your previous question got marked as a duplicate and looks very similar albeit a bit simpler - do you have code to show which you've developed from that point, which would get you half way to answering this question? Showing effort encourages better answers and helps narrow the problem down to a specific issue you're stuck on – Wolfie Nov 18 '22 at 16:46

1 Answers1

1

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.

MartinYakuza
  • 60
  • 1
  • 12
  • A slightly longer explanation with MATLAB code to calculate all combinations + quickly select random combinations can be found [in this answer of mine](https://stackoverflow.com/a/71599000/5211833). – Adriaan Nov 18 '22 at 15:18