Knapsack problem using Dynamic Programming

Question

Adam Stevens 2016-2-4

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/266697-knapsack-problem-using-dynamic-programming

评论： Walter Roberson 2018-10-19

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 个评论
显示无隐藏无

Hamed Hafizi 2018-10-19

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 2018-10-19

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

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Kiran 2016-2-12

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/266697-knapsack-problem-using-dynamic-programming#answer_209568

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

2 个评论
显示无隐藏无

Adam Stevens 2016-2-12

编辑：Walter Roberson 2016-2-12

在 MATLAB Online 中打开

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 2018-10-19

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?

请先登录，再进行评论。