How to find all the combinations of a vector elements whose sum is equal to a given number
11 vues (au cours des 30 derniers jours)
Afficher commentaires plus anciens
Valentina Mazzoni
le 8 Mai 2020
Commenté : Rami Matar
le 5 Oct 2020
Hi all,
I' ve got this vector made of 24 elements:
P = [250 500 500 1250 2500 5000 5000 15000 15000 15000 15000 8166 8926 9796 10800 11967 13333 14948 16875 16875 19200 22041 22041 25562 ]
and I've got a target value "n" to reach by combining a certain number of elements of P and adding them together:
n=3000 (it changes all the times because it's an input given by the user)
Every single element of the vector has to be taken just one time in the sum.
Do you have any ideas of how I can do it? Thanks.
0 commentaires
Réponse acceptée
Stephen23
le 8 Mai 2020
Modifié(e) : Stephen23
le 8 Mai 2020
A simple recursive nested function, with short-circuiting for combinations whose sums are greater than N (this makes the whole thing viable for small values of N and give results as quickly as possible):
function C = temp4(N)
P = [250,500,500,1250,2500,5000,5000,15000,15000,15000,15000 8166,8926,9796,10800 11967,13333,14948,16875,16875,19200,22041,22041,25562];
C = {};
for ii = 1:numel(P)
nestfun(P(ii),P(ii+1:end))
end
function nestfun(t,V)
if sum(t)<N
for jj = 1:numel(V)
nestfun([t,V(jj)],V(jj+1:end))
end
elseif sum(t)==N
C{end+1} = t;
end
end
end
Tested (the repeated vectors are due to the repeated values in P):
>> temp4(3000)
ans = {
[500 2500]
[500 2500]}
>> temp4(30000) % a much more interesting example
ans = {
[250 500 500 1250 2500 5000 5000 15000]
[250 500 500 1250 2500 5000 5000 15000]
[250 500 500 1250 2500 5000 5000 15000]
[250 500 500 1250 2500 5000 5000 15000]
[15000 15000]
[15000 15000]
[15000 15000]
[15000 15000]
[15000 15000]
[15000 15000]
[10800 19200]}
Note that if N is large then you can expect to be waiting for some time... e.g. given all 620,448,401,733,239,000,000,000 combinations at a rate of 1 million checks per second, you would have to wait around
>> yrs = 620448401733239000000000/1e6/60/60/24/365 % years
yrs = 19674289755.62021
>> num2words(yrs,'sigfig',1,'type','money','unit','Year|')
ans = twenty billion years
10 commentaires
Bruno Luong
le 4 Oct 2020
I guess you can replace P with Pr like this
>> P=1:5
P =
1 2 3 4 5
>> s=5
s =
5
>> Pr=repelem(P,floor(s./P))
Pr =
1 1 1 1 1 2 2 3 4 5
Then use Stephen's algorithm on Pr.
Plus de réponses (0)
Voir également
Catégories
En savoir plus sur Resizing and Reshaping Matrices dans Help Center et File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!