function [ub,lb] = knapsack(weights,values,max_weight)
% Provides upper and lower bounds on the solution to a 
% knapsack problem. Arguments weights and values are
% column vectors representing the characteristics of
% items in a knapsack. Argument, max_weight is a scalar
% representing the maximum aggregate weight of selected
% items

ub = getUB(weights,values,max_weight);
lb = getLB(weights,values,max_weight);

function ub = getUB(weights,values,max_weight)
	prob = [];
	prob.f = -values;
	prob.Aineq = transpose(weights);
	prob.bineq = max_weight;
	prob.lb = spalloc(length(weights),1,0);
	prob.ub = ones(size(weights));
	prob.x0 = [];
	prob.options = optimset('LargeScale','on');
	prob.solver = 'linprog';
	[X,fval,exitflag,output,lambda] = linprog(prob);
	ub = sum(X .* values);

function lb = getLB(weights,values,max_weight)
	[Y,I] = sort(values(find(weights <= max_weight)),'descend');
	best_single_value = Y(1);

	eps = 0.0;
	effic = values ./ (weights);
	[Y,I] = sort(effic,'descend');
	if weights(I(1)) > max_weight, 
		lb = best_single_value;
	else,
		i = 1;
		while and(i<length(weights),sum(weights(I(1:i))) + eps < max_weight), 
			i = i + 1;
		end

		if best_single_value > sum(values(I(1:i))),
			lb = best_single_value;
		else,
			idxs = I(1:i-1);
			lb = sum(values(I(1:i-1)));
		end
	end