Sum minimum n matrix elements > certain value

4 次查看（过去 30 天）
Paul Reinders
Paul Reinders 2017-9-5
评论： Paul Reinders 2017-9-5
Hello,
My problem is about matrices, for example a 20x20 size.
I would like to know how to: - determine which combinations of values are > than a given sum.
Some constrains must be taken in consideration:
- from each column only 1 value can be used
- a combination (sum) of values should have at least 3 values
Example of 6x6
4 5 7 3 8 4
1 8 4 2 1 3
9 1 8 3 5 7
5 5 7 3 3 4
1 8 4 2 1 3
8 1 6 3 0 15
Question: How to find all unique combinations of values that are > 15.
If the matrix is 20x20 brute force is not really an option. There are simple to many combinations.
Thank you very much for your help.
  2 个评论
Paul Reinders
Paul Reinders 2017-9-5
I'm not a mathematician and I don't have matlab experience. I searched the internet for a similar case, try to find an algorithm but could not find anything helpful.
Until now I have tried to find all the possible unique descending combinations with a least 3 elements and the sum > than the given value.

请先登录，再进行评论。

请先登录，再回答此问题。

回答（1 个）

John D'Errico
John D'Errico 2017-9-5
Not all problems have a simple solution. In fact, it is trivial to pose simple looking problems that have such a huge search space that either you will never stop looking for a solution, or you will generate so many possible solutions that you will run out of memory to store them all.
Sadly, this problem is a case where both of those issues are involved. The search space is huge, and there will probably be so many solutions that you will run out of memory to hold them all.
Often the correct solution is to ask yourself if you REALLY DO need all such solutions. Or if you really need to solve this problem at all.
Note that you CAN view this problem as one where you take each column, and put a tick mark on a corresponding axis of your search space. Add a tick for 0 on each axis too. So with 20 columns, you have 20 dimensions. For the 6x6 case you show...
4 5 7 3 8 4
1 8 4 2 1 3
9 1 8 3 5 7
5 5 7 3 3 4
1 8 4 2 1 3
8 1 6 3 0 15
The first axis will have ticks at [0 1 4 5 8 9], the second axis at [0 1 5 8], the third axis has ticks at [0 4 6 7 8], etc.
Now, visualize a lattice in all 6 (oe 20) dimensions, passing through all combinations of those ticks, thus something that ndgrid would generate.
So something like this:
[X1,X2,X3,X4,X5,X6] = ndgrid([0 1 4 5 8 9],[0 1 5 8],[0 4 6 7 8],[0 2 3],[0 1 3 5 8],[0 3 4 7 15]);
Finally, visualize a plane that lives in that space, defined by the condition
x1 + x2 + x3 + x4 + x5 + x6 >= 15
Any vertices of the lattice that live on the correct side of your plane correspond to solutions. A solution with zero in it does not use the corresponding column. If you add in the final constraint that there must be at least three columns selected, this just means you will only accept solutions with at least 3 non-zeros in it.
Finally, you would need to deal with the case where as is here, the 5th column actually has a zero in it.
Again though, in 20 dimensions, no matter how you phrase it, the search space is simply too huge in 20 dimensions.
[X1,X2,X3,X4,X5,X6] = ndgrid([0 1 4 5 8 9],[0 1 5 8],[0 4 6 7 8],[0 2 3],[0 1 3 5 8],[0 3 4 7 15]);
X = [X1(:),X2(:),X3(:),X4(:),X5(:),X6(:)];
size(X)
ans =
9000 6
So there are 9000 nodes in the 6 dimensional lattice.
ind = find((sum(X,2) >= 15) & ((sum(X > 0,2) >= 3) | ((sum(X > 0,2) == 2) & (X(:,5) == 0))));
ans =
7907
And there are 7907 solutions, just for the 6 column case.

类别

在 Help Center 和 File Exchange 中查找有关 Creating and Concatenating Matrices 的更多信息

标签

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by