Make sure the number X can be generated based on the combination of the series (a, b, c)
I'm going crazy trying to figure out how to make a program that doesn't try every combination. Simple example: I want to know if it is possible to create 11 by adding numbers from the series (2,5,10,20), is there an easy way to do this without trying every possibility? In this case, we can do it with three 2s and 5. Thanks
source to share
I think I worked out some kind of solution
- You must order your list from higher to lower. This gives us [20, 10, 5, 2]
- Then we're going to work with some kind of stack.
start with n = 0
and. you will push the nth element of your list to the top of the stack.
b. If the sum of the numbers on your stack is greater than the target number, you pop the last element of your stack and return to point a. with n = n + 1. if the item you are popping from the stack is your lower number, then you also remove the item below and return to point a. with n = (index of the last remote number in your set) +1
from. if it doesn't, you try to add it again and go back to point b.
this algorithm is recursive, it stops when you pop the last number from your stack and that number is your lower number (then you cannot generate a number from your set) or when the sum of the numbers in your stack equals your target number (then you you can generate it from your set)
run example: target 11, set [20,10,5,2]
- Stack state: empty, n = 0
- push 20 on the stack: stack state: [20]> 11, removing 20 from stack => n = 1
- put 10 on the stack: stack state: [10] 11, n = 1
- put 10 on the stack: stack state: [10, 10]> 11, removing 10 from stack => n = 2
- push 5 onto the stack: stack state: [10,5]> 11, remove 5 from stack => n = 3
- push 2 on the stack: stack state: [10,2]> 11, remove 2 and 10 from the stack => n = 2
- push 5 onto the stack: stack state: [5] <11, n = 2
- put 5 on the stack: stack state: [5,5] <11, n = 2
- put 5 on the stack: stack state: [5,5,5]> 11, removing 5 from stack => n = 3
- put 2 on the stack: stack state: [5,5,2]> 11, removing 2 and 5 from the stack => n = 3
- push 2 onto the stack: stack state: [5,2] <11, n = 3
- push 2 onto the stack: stack state: [5,2,2] <11, n = 3
- put 2 on the stack: stack state: [5,2,2,2] = 11, you win
source to share
One way to do this is to formulate the LP / IP model. Here's an optimization model (coded using ojAlgo) that minimizes the total number of terms.
final Variable tmpVar02 = new Variable("02").weight(1.0).lower(0.0).integer(true);
final Variable tmpVar05 = new Variable("05").weight(1.0).lower(0.0).integer(true);
final Variable tmpVar10 = new Variable("10").weight(1.0).lower(0.0).integer(true);
final Variable tmpVar20 = new Variable("20").weight(1.0).lower(0.0).integer(true);
final ExpressionsBasedModel tmpModel = new ExpressionsBasedModel();
tmpModel.addVariable(tmpVar02);
tmpModel.addVariable(tmpVar05);
tmpModel.addVariable(tmpVar10);
tmpModel.addVariable(tmpVar20);
final Expression tmpRequired = tmpModel.addExpression("Required").level(11.0);
tmpRequired.setLinearFactor(tmpVar02, 2.0);
tmpRequired.setLinearFactor(tmpVar05, 5.0);
tmpRequired.setLinearFactor(tmpVar10, 10.0);
tmpRequired.setLinearFactor(tmpVar20, 20.0);
final Result tmpResult = tmpModel.minimise();
System.out.println(tmpResult);
System.out.println();
System.out.println(tmpModel);
Running the code produces this result: OPTIMAL 4.0 @ [3.0, 1.0, 0.0, 0.0]
source to share