Find minimal possible term x by trying out various combinations of other terms for a known sum
3 views (last 30 days)
Show older comments
Vladislavs Grigorjevs
on 4 Apr 2022
Commented: Bruno Luong
on 4 Apr 2022
Hello!
This will be a 2 part question.
- So let's say I have a known sum, s=12 for example. I also have a number of terms that can all be part of this sum - a, b, c, d and so on, each of them having a constant numeric value assigned to them (for example, a=2; b=3.5; c=1.79 etc.). There is a term x that is a part of this sum as well, but it is unknown and I need it to be as low as possible. So, essentially, I need a code that would try out different combinations of a, b, c etc. in order to find one where x would be the smallest possible value, assuming that the sum stays constant. It should be noted that a single term should also be able to be used multiple times in the sum if it makes sense to do so (for example s = a + a + a + ... + x).
- Now, each term will have a defined quantity of times it can be used (for example a can be used 128 times, b can be used 64 times and so on). When the most optimal combination has been used the maximum amount of times for one of the terms, the second most optimal combination of the terms needs to be found, with the term that has run out bypassed. I need this to be repeated until all of the terms have run out. Also, if a situation arises where the most optimal combination is s = a + a + a + ... + x, but a only has 2 times left to be used, then the combination must be adapted so that there aren't any leftovers (as in each term should always be used all of the available amount of times).
I need each combination and the amount of times it is used displayed to me in chronological order as a return. How would I go about making a script like this? I am not familiar with coding that well and it is a bit hard for me to wrap my head around it, so any help would be greatly appreciated.
0 Comments
Accepted Answer
Bruno Luong
on 4 Apr 2022
You need first to formulate your problem in consist unambiguous math problem.
So I unstand you have an array
A with n-numbers (in your case = [a, a, ..., a, b, b...] with a repeated 128 times, b 64 times).
What you want is to find a subset S of A and x such that
sum(S) + x = s, and you want x (>=0?) is as small as possible.
This problem can be formulated as interger linear programming. Find
array w of same size as A, w having elements of value 0 or 1, such that
x(w) := abs(s - w.*A) is smallest as possible.
12 Comments
Bruno Luong
on 4 Apr 2022
"That doesn't seem to work"
Check what to do by reading
doc Intlinprog
More Answers (1)
Davide Masiello
on 4 Apr 2022
Edited: Davide Masiello
on 4 Apr 2022
This may be an approach
a = 2; % Can be repeated 128 times max
b = 3.5; % Can be repeated 64 times max
c = 1.79; % Can be repeated 32 times max
S = 50; % The sum
A = combntns(1:128,3); % All possible combintations of 3 numbers between 1 and 128
A(A(:,2)>64 & A(:,3)>32,:) = []; % Rules out if # of repetitions of b and c is over max number allowed
x = S-A*[a;b;c]; % Finds x
x(x<0) = +inf; % Rules out all x<0
[xmin,idx] = min(x); % Finds the samllest x
fprintf('The best combination is %i x a + %i x b + %i x c. The value of x if %f.\n',[A(idx,:),xmin])
2 Comments
Davide Masiello
on 4 Apr 2022
Yes, in such a large case my example wouldn't be suitable because the matrix of all possible combinations becomes too large and matlab runs out of memory.
In this case I would rather opt for the suggestions given by @Bruno Luong in his answer, which has a more rigorous mathematical approach.
See Also
Categories
Find more on Loops and Conditional Statements in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!