Knapsack problem using Dynamic Programming

23 次查看（过去 30 天）
Adam Stevens
Adam Stevens 2016-2-4
评论： 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
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?

请先登录，再进行评论。

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

采纳的回答

Kiran
Kiran 2016-2-12
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
Adam Stevens 2016-2-12
编辑：Walter Roberson 2016-2-12
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 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?

请先登录，再进行评论。

更多回答（0 个）

类别

在 Help Center 和 File Exchange 中查找有关 Particle Swarm 的更多信息

标签

Community Treasure Hunt

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

Start Hunting!

Translated by