News for hackers. Stuff that matters.
Re:Algorithms, A Dropbox Challenge and Dynamic Programming by NY_USA_Hacker on Sunday February 27, 2011 @10:01AM (#2267932)
So, for the problem, we are given some positive integer n and, for i = 1, 2, ..., n, numbers a(i).

So, we seek x(i) to solve

     min ( x(1) a(1) + x(2) a(2) + ... + x(n) a(n) )^2

     x(1) + x(2) + ... + x(n) >= 0

     subject to x(i) = 0, 1
So this is a 0-1 integer quadratic program with one linear constraint.

So for a reasonably practical solution, omit the 0-1 constraint and attack the problem as just a quadratic program.

Then for the 0-1 constraint, do standard branch and bound.

There are no comments on this comment yet.