Optimization: principles and algorithms, by Michel Bierlaire
knapsackGreedy.m
Go to the documentation of this file.
1 %> \file
2 %> Solves the knapsack problem using the greedy heuristic described in section 27.1.1 of \cite Bier15-book
3 %>
4 %> @note Tested by run2702greedy.m
5 %>
6 %> @author Michel Bierlaire
7 %> @date Tue Apr 14 11:22:01 2015
8 %> @ingroup Algorithms
9 %> @ingroup chap27
10 
11 function xopt = knapsackGreedy(u,w,capacity)
12  [n,shouldBeOne] = size(u) ;
13  if (shouldBeOne != 1)
14  error("A column vector is expected for u") ;
15  endif
16  [nw,shouldBeOne] = size(w) ;
17  if (shouldBeOne != 1)
18  error("A column vector is expected for w") ;
19  endif
20  if (nw != n)
21  error("The two vectors must have the same size")
22  endif
23  xopt = zeros(n,1) ;
24 
25  ratio = -u ./ w ;
26 
27  [ sorted, index] = sort(ratio) ;
28 
29  totalWeight = 0 ;
30 
31  for i = 1:n
32  elem = index(i) ;
33  if (totalWeight + w(elem) <= capacity)
34  xopt(elem) = 1 ;
35  totalWeight += w(elem) ;
36  endif
37  endfor
38 
39 endfunction
function knapsackGreedy(in u, in w, in capacity)
Copyright 2015-2016 Michel Bierlaire