MATLAB Answers

Knapsack problem using Dynamic Programming

232 views (last 30 days)
Adam Stevens
Adam Stevens on 4 Feb 2016
Commented: Walter Roberson on 19 Oct 2018
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
  2 Comments

Sign in to comment.

Accepted Answer

Kiran
Kiran on 12 Feb 2016
Check following link for complete implementation of 0/1 Knapsack problem on MATLAB central.
  2 Comments
Hamed Hafizi
Hamed Hafizi on 19 Oct 2018
I am really seeing how to coding unbounded knapsack( to take one item more than one) in Matlab, is there anyone to code this type of knapsack in Matlab?

Sign in to comment.

More Answers (0)

Categories

Community Treasure Hunt

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

Start Hunting!