Knapsack problem using Dynamic Programming

31 views (last 30 days)
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
Hamed Hafizi
Hamed Hafizi on 19 Oct 2018
Hello every one 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.

Accepted Answer

Kiran
Kiran on 12 Feb 2016
Check following link for complete implementation of 0/1 Knapsack problem on MATLAB central.
  2 Comments
Adam Stevens
Adam Stevens on 12 Feb 2016
Edited: Walter Roberson on 12 Feb 2016
Thanks Kiran,
I was also able to figure out my example which is not just 0/1 (can be any non-negative integer). I added a matrix to memoize the values as they were determined. Then go forward with the first answer to the last looking up answers in the memo table. (The only thing I don't like about it is my use of for loops. It would be nice to have a vectorized solution.) Here is my code:
clear all;
global N w r c memo;
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
memo = [];
V = Val(1,c)
b=c;
items = zeros(1,N);
for k=1:N
items(k) = memo(find(memo(:,1)==k & memo(:,2)==b,1),3);
b=b-w(k)*items(k);
end
items
function V = Val(k,b)
global N w r memo;
% 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,idx] = max(r(k)*p); % base case
memo = [memo; [k,b,p(idx)]];
else
temp = zeros(1,length(p));
for n=1:length(p)
% value of k+1 item given budget if p number of item k used
temp(n) = Val(k+1,b-w(k)*p(n));% recursion step
end
[V,idx] = max(r(k)*p + temp);
memo = [memo; [k,b,p(idx)]];
end
end
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)

Community Treasure Hunt

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

Start Hunting!