Knapsack problem using Dynamic Programming

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

[Hamed Hafizi]

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?

[Walter Roberson]

Perhaps https://www.mathworks.com/matlabcentral/fileexchange/20436-multi-knapsack-solver -- you could always just use one knapsack ?

Answer 1

[Kiran]

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

http://in.mathworks.com/matlabcentral/fileexchange/22783-0-1-knapsack/content/knapsack.m

[Adam Stevens]

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]

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?