Find minimal possible term x by trying out various combinations of other terms for a known sum
3 次查看(过去 30 天)
显示 更早的评论
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 个评论
采纳的回答
Bruno Luong
2022-4-4
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 个评论
Bruno Luong
2022-4-4
"That doesn't seem to work"
Check what to do by reading
doc Intlinprog
更多回答(1 个)
Davide Masiello
2022-4-4
编辑:Davide Masiello
2022-4-4
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 个评论
Davide Masiello
2022-4-4
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.
另请参阅
类别
在 Help Center 和 File Exchange 中查找有关 Loops and Conditional Statements 的更多信息
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!