0
$\begingroup$

I have an equation $x = 3a+4b+2c+4d$, where $a$, $b$, $c$ and $d$ are nonnegative integers such that $a+b+c+d=5$. What algorithm can I use to calculate maximum value of $x$?

$\endgroup$
  • $\begingroup$ My question is how can I divide 5 into a, b, c ,d such that the value of the equation is maximum, and I already wrote that a, b, c ,d are whole. $\endgroup$ – Varun Saproo Jun 22 '17 at 15:00
  • $\begingroup$ @VarunSaproo, if you don't introduce additional constraint similar to what Rick Decker suggests, then there is no maximum. $\endgroup$ – fade2black Jun 22 '17 at 15:11
  • 3
    $\begingroup$ @VarunSaproo I've clarified your statement of the problem based on my interpretation of your comment. But I'm still not sure what your question really is. There are so few possible solutions to $a+b+c+d=5$ that you can just try all the possibilities. Are you only interested in this pair of equations, or do you want to solve more general problems of a similar type. If you want to solve more general problems, what class of problems are you actually interested in? $\endgroup$ – David Richerby Jun 22 '17 at 16:48
1
$\begingroup$

Non-negative means that they can be 0. So set everything to $0$ except $b$ and $d$ because they have the highest coefficient.

$x=3*0+4b+2*0+4d$ and $0+b+0+d=5$

$x=4b+4d$ and $b+d=5$

$x=4(b+d)$ and $b+d=5$

$x = 4*5 = 20$

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Your problem is a special case of the integer programming problem which is known to be NP-complete. One possible approximation is branch-and-bound algorithm. However, if you have only 4 variables $a,b,c,d$ and and additional constraint such as $a,b,c,d \geq const$, then why not try brute force? In case $const =0$ you would have only $6^4 = 1296$ possibilities.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.