backtrack1.m

This function implements brute force bactracking to solve the knapsack problem.

function [optP,optX,r]=backtrack1(l,x,w,p,optP,optX,M,r)

% Invocation: [optP,optX,r]=backtrack1(l,x,w,p,optP,optX,M,r)
% Parameters: l: the recursive level, initialise to 1
%             x: current value of x, initilaise to all zeros
%             w: the vector of weigths
%             p: the vector of profits
%          optP: the optimal profit, initialise to 0
%          optX: the optimal value for X, initialise to []
%             M: the maksimum weight
%             r: number of calls to the function, init. to 1
% 
% This function implements brute force bactracking to solve
% the knapsack problem.
%
% Copyright Lars Aurdal/Rikshospitalet
  
  % Get length of vector
  w=1;
  M=9;
  r=1;
  x=0;
optX=[];
optP=0;
p=2;
  l=1;
  n=200;
  n=length(w);
  
  % If at bottom of the recursion
  
  if(l>n)
    r=r+1;    % Increnet the number of calls
    
    % Calculate the current weigth
    
    tmpW=0;   
    for(i=1:n)
      tmpW=tmpW+w(i)*x(i);
    end
    
    % If current weigth is less than max weigth
    % calculate current profit
    
    if(tmpW <= M)
      tmpP=0;
      for(i=1:n)
	tmpP=tmpP+p(i)*x(i);
      end
      
      % If current profit exceeds current max profit
      
      if(tmpP>optP)
	optP=tmpP;
	optX=x;
      end
    end
  else
    
    % If not at bottom of recursion begin by exploring
    % the 1-branch
    
    x(l)=1;
    [optP,optX,r]=backtrack1(l+1,x,w,p,optP,optX,M,r); 
    
    % Then explore the 0-branch
    
    x(l)=0;
    [optP,optX,r]=backtrack1(l+1,x,w,p,optP,optX,M,r);   
  end