232 views (last 30 days)

Show older comments

I wrote a matlab code to solve a knapsack problem and can get the optimal value of the knapsack but I am trying to figure out how to return the list of items that would lead to this optimal value. Can anyone help me see an easy way to do this?

global N w r c items;

N=3; % number of different items to chose from

w = [3,8,5]; % weights of each item

r = [4,6,5]; % value of each item

c = 8; % total weight that can be carried

V = Val(1,c)

function V = Val(k,b)

global N w r;

% N - number of different items

% w - array of weights for each item

% r - array of values for each item

m = floor(b/w(k)); % determine max number of item k for budget b

p = 0:m; % array of possible numbers of each item given budget b

if k==N

V = max(r(k)*p); % base case

else

temp = zeros(1,length(p));

% recursion step

for n=1:length(p)

% value of k+1 item given budget remaining if p number of item k is

% used

temp(n) = Val(k+1,b-w(k)*p(n));

end

V = max(r(k)*p + temp);

end

end

Walter Roberson
on 19 Oct 2018

Kiran
on 12 Feb 2016

Check following link for complete implementation of 0/1 Knapsack problem on MATLAB central.

Hamed Hafizi
on 19 Oct 2018

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!