Path: news.mathworks.com!not-for-mail
From: <HIDDEN>
Newsgroups: comp.soft-sys.matlab
Subject: solve dot(x,y)<=z  for x
Date: Mon, 19 Jan 2009 16:22:01 +0000 (UTC)
Organization: The MathWorks, Inc.
Lines: 39
Message-ID: <gl29b9$6tb$1@fred.mathworks.com>
Reply-To: <HIDDEN>
NNTP-Posting-Host: webapp-03-blr.mathworks.com
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: 8bit
X-Trace: fred.mathworks.com 1232382121 7083 172.30.248.38 (19 Jan 2009 16:22:01 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Mon, 19 Jan 2009 16:22:01 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 1582760
Xref: news.mathworks.com comp.soft-sys.matlab:512499


Hello, Happy new year.

I would appreciate your advice...

Problem:  solve dot(x,y)<=z  for x, list all solutions

Input (knowns):  z: a positive real number (scalar)
                         y: a n-d vector of positive numbers, sorted in ascending order

Output(unknowns)  x : a n-d vector of non-negative integers

Basic idea of my solution:  I lexicographically list out the candidates for solutions, while checking the condition  "dot(x,y)<=z".

For example,  z = 3.8,  y =[1.213, 2.142, 3.112], 

my code would be

y=[1.213, 2.142, 3.112];
z =3.8;
n= length(y);                        % dimension of input vector y
x= zeros(1,n);                       % solution vector x
X = [];                                  % matrix storing all solution vectors x
flag =1;
while  flag ==1
    X = [X; x];    
    flag =0;
    for j= n:-1:1
        if  dot (x (1:j), y(1:j))+ y(j) <= z
            x(j+1:n) =0;
            x(j) = x(j)+1;
            flag = 1;
            break
        end
    end
end
X                                            % display the solution

It works quite fast, for moderate n and z.  But since I tend to always use less efficient approach, I would like to hear your opinions about it.