Knapsack problem using Dynamic Programming

23 Ansichten (letzte 30 Tage)
Adam Stevens
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
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?

Melden Sie sich an, um zu kommentieren.

Akzeptierte Antwort

Kiran
Kiran am 12 Feb. 2016
Check following link for complete implementation of 0/1 Knapsack problem on MATLAB central.
  2 Kommentare
Adam Stevens
Adam Stevens am 12 Feb. 2016
Bearbeitet: Walter Roberson am 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 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?

Melden Sie sich an, um zu kommentieren.

Weitere Antworten (0)

Community Treasure Hunt

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

Start Hunting!

Translated by