mathematical-optimization , Verify if a number X can be generated based on a combination of a series (a,b,c)

## Question:

Tag: mathematical-optimization

I'm going crazy trying to figure out a way to make a program that does not try every single combination. A simple example: I want to know if 11 can be generated by adding up numbers from the series (2,5,10,20), is there an easy way to do this without trying every single possibility? In this case we can do it with three 2s and one 5. Thanks

I think I worked up some kind of a solution

1. You must order your list, from higher to lower. It gives us [20, 10, 5, 2]
2. Then, we're gonna work with some kind of a stack.

we begin with n=0

a. you put the n'th element of your list at the top of the stack.

b. If the sum of numbers into your stack is greater than the targeted number, you remove the last element of your stack and return to point a. with n=n+1. if the element you remove from the stack is your lower number, then you also remove the element below, and return to point a. with n=(index of last removed number in your set)+1

c. if it is not, you try to add it one more time, and return to point b.

d. this algorithm is recursive, it stops when you remove the last number from your stack, and this number is your lower number (then you can't generate the number from your set), or when the sum of numbers in your stack is equal to your target number (then you can generate it from your set)

run example : target 11, set [20,10,5,2]

• stack status : empty, n=0
• put 20 into stack : stack status : [20] > 11, removing 20 from stack => n=1
• put 10 into stack : stack status : [10] < 11, n=1
• put 10 into stack : stack status : [10, 10] > 11, removing 10 from stack => n=2
• put 5 into stack : stack status : [10,5] > 11, removing 5 from stack => n=3
• put 2 into stack : stack status : [10,2] > 11, removing 2 and 10 from stack => n=2
• put 5 into stack : stack status : [5] < 11, n=2
• put 5 into stack : stack status : [5,5] < 11, n=2
• put 5 into stack : stack status : [5,5,5] > 11, removing 5 from stack => n=3
• put 2 into stack : stack status : [5,5,2] > 11, removing 2 and 5 from stack => n=3
• put 2 into stack : stack status : [5,2] < 11, n=3
• put 2 into stack : stack status : [5,2,2] < 11, n=3
• put 2 into stack : stack status : [5,2,2,2] = 11, You Won

# Related:

## Is it necessary the two curves are crossing each other if I want to solve two equations with two unknown paramters? [closed]

math,mathematical-optimization,curve-fitting
I have two curves as show in this figure: I have two equations of these curves with two unknown parameters, but I want to know is it necessary for these two curves to cross each other to be solved? or it is not necessary to be crossed? Because I want...

## Best way on Java to perform a basic operation with Long [closed]

java,optimization,mathematical-optimization
I have a Long number of 10 digits and I want to now the best way to implement this check. I'll explain it with an example: If we have the number 3456789123: 3 will be multiplied by 10. 4 will be multiplied by 9. 5 will be multiplied by 8....

## How to convert quadratic to linear program?

I have an optimization problem that has in the objective function 2 multiplied variables, making the model quadratic. I am currently using zimpl, to parse the model, and glpk to solve it. As they don't support quadratic programming, I would need to convert this to an MILP. . The first...

## Integer programming: assignment of absolute value (depending on variable value)

optimization,mathematical-optimization,linear-programming,scientific-computing,integer-programming
I am relatively new to integer programming and (again) got stuck with the formulation of a constraint. In my simplified model I have a (continous) variable with a lower bound LB below zero and an upper bound UB above zero. Now I want to assign the variable value to other...

## How to replicate excel solver in R

r,excel,mathematical-optimization
I used excel solver to solve an optimization problem, and I am trying to replicate it in R. I found many packages like optim, ROI etc., but it seems all of them only take a vector as the object to optimize and allow the variables to take any continuous value....

## Finding a vector that is approximately equally distant from all vectors in a set

python,vector,linear-algebra,mathematical-optimization,approximate
I have a set of 3 million vectors (300 dimensions each), and I'm looking for a new point in this 300 dim space that is approximately equally distant from all the other points(vectors) What I could do is initialize a random vector v, and run an optimization over v with...

I have a vector A of length N. Also I have N*N matrix C. I want to maximize following equation : minimize (- (w_transpose * A) + p * w_transpose * C * w) Where w is a vector of length N, with constraints that each w is non-negative and...

## How to find more clever algorithm to check pairs of primes to see if paired they produce another prime?

ruby,algorithm,primes,mathematical-optimization
I am stuck on Project Euler question 60. I know it is advised not too ask questions or find answers online about it, but otherwise I cannot find the motivation to continue. So I hope to find some help here which can make me go forward. So long for the...

## Fitting circle inside image. Exit condition for loop

python,image-processing,optimization,numpy,mathematical-optimization
I am trying to write some code to check if my circle fits inside a binary mask. So, I have a circle with a given center and a radius. I also have a binary image and I can plot it and see that the circle fits inside the mask. The...

## Gurobi in python to calculate lp norm

python,mathematical-optimization,gurobi
Gurobi in python to calculate l1 norm I am trying to calculate l1 norm by using Gurobi in python. Since I am new to python and Gurobi, I am here to ask for help. The model is: minimize 1^T(r+ + r-) s.t. y - X beta = r+ - r-...

## R function solve.QP error “constraints are inconsistent, no solution!”

r,mathematical-optimization
I am trying to run an optimzation by using the solve.QP function (from the quadprog package) with the following parameters R = matrix( c( 2.231113e-05,-4.816095e-05,-5.115287e-05, 0,2.989584e-05,4.212173e-06,0,0, 5.504990e-05), ncol=3, byrow=T) b = c(-1,0,rep(0,ncol(R))) C = cbind(rep(1,ncol(R)), diag(ncol(R))) C = cbind(-rep(1,ncol(R)),C) d = as.matrix(c(57621264,78057622,171342351),ncol=1) H = solve.QP(Dmat = R, factorized = TRUE,...

## P^N Combinaisons with Integers (Kernel), how to generate them?

java,math,complexity-theory,mathematical-optimization,algebra
My question is almost the same that the one I asked few months ago : 2^N Combinaisons with Integers (Kernel), how to generate them? Basically, I wanted to have the 2^N combinaisons inside a Kernel, but I generalized my version, and now it's even more complicated : I don't want...

## Using sapply (or apply) inside objective function for optim ; object in list element no longer recognized

r,apply,mathematical-optimization,sapply
I would like to use an objective function based on a list of elements, each of which is the result of applying a function over a dataframe (df) ((function is, say, variance of df's observations' "measure")). That is, I have a list of dfs. I naturally want to sapply my...

## Finding optima of PolynomialFunction in commons.math

java,mathematical-optimization,apache-commons-math
Is there a simple way to find the optimum of a PolynomialFunction (which is also a UnivariateDifferentiableFunction) in commons.math? There are a bewildering array of multidimensional optimizers, but AFAICS the only explicitly univariate optimizer is Brent, which doesn't take advantage of the differentiability.

## How can I minimize this function in R?

r,function,optimization,mathematical-optimization
I'm attempting to write a formula that will determine a value of a that minimizes the function output myfun (i.e. a-fptotal). MWE: c <- as.matrix(c(.25,.5,.25)) d <- as.matrix(c(10000,12500,15000)) e <- 700 f <- 1.1 tr <- .30 myfun <- function(a) { b <- max(a-e,0) df <- data.frame(u1=c(c*b*.40),u2=c(c*b*.60)) df\$year <- 1:nrow(df)...

## What is the logic of this process

python,math,while-loop,mathematical-optimization,python-3.4
I was working on a problem in Project Euler; and I found a question in SO. The question and accepted answer says; n = 600851475143 i = 2 while i * i < n: while n%i == 0: n = n / i i = i + 1 print (n)...

## Finding a large non-sparse submatrix in a large sparse matrix

algorithm,matrix,mathematical-optimization
I have a very large N x P binary matrix, and I'd like to find two sets R and C which contain the indexes of the rows and columns that make up the largest possible dense (non-sparse, made up of only 1's) submatrix, which meets at least a certain size...

## R: Isotonic regression Minimisation

r,regression,mathematical-optimization,linear-programming,minimization
I want minimize the following equation: F=SUM{u 1:20}sum{w 1:10} Quw(ruw-yuw) with the following constraints: yuw >= yu,w+1 yuw >= yu-1,w y20,0 >= 100 y0,10 >= 0 I have a 20*10 ruw and 20*10 quw matrix, I now need to generate a yuw matrix which adheres to the constraints. I am...

## Matlab: Binary Linear Programming

matlab,matrix,binary,integer,mathematical-optimization
I am trying to solve some equations on Matlab using Binary Integer Programming. I have 3 sets of equations: Ma.X=1 Mp.X<=1 Mr.X<=m* Where, Ma is a known matrix with size 5*12 X is unknown set with size 12*1 Also Mp is known matrix with size 5*12 and Mr is a...

## R optimization with equality and inequality constraints

r,statistics,mathematical-optimization,minimization
I am trying to find the local minimum of a function, and the parameters have a fixed sum. For example, Fx = 10 - 5x1 + 2x2 - x3 and the conditions are as follows, x1 + x2 + x3 = 15 (x1,x2,x3) >= 0 Where the sum of x1,...

## data fitting an ellipse in 3D space

matlab,mathematical-optimization,ellipse,data-fitting
Forum I've got a set of data that apparently forms an ellipse in 3D space (not an ellipsoid, but a curve in 3D). Being inspired by following thread http://au.mathworks.com/matlabcentral/newsreader/view_thread/65773 and with the help from someone ,I manage to get the optimization code running and outputs a set of best parameters...

## How to generate an optimal order of multiple elements based on pairwise element score values

python,optimization,order,mathematical-optimization
I have a number of elements, let say [a, b, c, d], and for each pairwise combination I have a score: [['d-a', 0], ['a-b', 0], ['b-a', 0], ['a-c', 2], ['c-a', 0], ['a-d', 2], ['d-b', 1], ['b-c', 2], ['c-b', 0], ['b-d', 2], ['d-c', 2], ['c-d', 2]] I am looking for a...

## R linear model with constraints

r,mathematical-optimization,linear
I want to fit a linear model y ~ a_1 * x_1 + ... + a_n * x_n with parameter constraints a_1,...,a_n >=0 and a_1 + ... + a_n <= 1 in R. Is there an elegant and fast way to do that and without using solve.QP of the quadprog...

## Efficient method of extracting a point from a 3D plane

math,3d,mathematical-optimization,plane
I've come across this method of extracting a location from a 3D plane. I've tested this and it works correctly, but for such a primitive operation, I was wondering if there was a, more efficient method in common practice. void position_from_plane(float r_co[3], const float p[4]) { const float p_len_sq =...

## cumulative Distribution function error in indoor localization

matlab,math,mathematical-optimization,indoor-positioning-system
How I'm just wondering if somebody can explain about how can we get the CDF error for indoor localization as in example I found this quote in one of the paper "Usually, the cumulative probability functions (CDF) of the distance error is used for measuring the precision of a system....

## Mixed integer programming: variable assignment per condition (if then else)

optimization,mathematical-optimization,linear-programming,scientific-computing,integer-programming
I am relatively new to (mixed) integer programming and got stuck with the formulation of a constraint. In my simplified model I have one Parameter and two Variables that are positive Reals having the value 321 as upper bound. The logic I want to express is here: if Parameter >...

## About correct notation of pareto dominance in optimization

math,mathematical-optimization,genetic-algorithm
I search the correct notation of Pareto Dominance, but i don't know if it is a question for Mathexchange or here.. In multiple papers, like the classic Deb nsga2 paper, you can found the pareto dominance relation written like this A dominate B if In wikipedia, or other paper, like...

## Optimization in R: Maximizing and Minimizing Many Variables

r,ggplot2,mathematical-optimization,minimize,maximize
I have a dataset with 70 foods and information about each food's nutritional value (protein/oz., fat/oz., cals/oz., etc.), as well as the food's cost/oz. I am trying to figure out--given a set budget in \$--what the best combination of foods (and the amt. of each food) would be to maximize...