Knapsack problem using Dynamic Programming
23 Ansichten (letzte 30 Tage)
Ältere Kommentare anzeigen
Adam Stevens
am 4 Feb. 2016
Kommentiert: Walter Roberson
am 19 Okt. 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 Kommentare
Hamed Hafizi
am 19 Okt. 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?
Walter Roberson
am 19 Okt. 2018
Perhaps https://www.mathworks.com/matlabcentral/fileexchange/20436-multi-knapsack-solver -- you could always just use one knapsack ?
Akzeptierte Antwort
Kiran
am 12 Feb. 2016
Check following link for complete implementation of 0/1 Knapsack problem on MATLAB central.
2 Kommentare
Hamed Hafizi
am 19 Okt. 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?
Weitere Antworten (0)
Siehe auch
Kategorien
Mehr zu Particle Swarm finden Sie in Help Center und File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!