function [X, reward] = DPKnapsack(value, weight, capacity)
% preallocate tables
numItems = length(value);
valueTable = zeros(1+capacity,numItems);
decisionTable = zeros(1+capacity,numItems);
capValues = (0:capacity)'; % this is for convenience
% Initialize last column of tables
decisionTable(:,numItems) = (capValues >= weight(numItems));
valueTable(:,numItems) = decisionTable(:,numItems) * value(numItems);
% Backward loop on items (columns in the value table)
for k=(numItems-1):-1:1
    % Loop on rows (state: residual budget)
    for residual = 0:capacity
        idx = residual+1; % MATLAB starts indexing from 1....
        if residual < weight(k)
            % cannot insert
            decisionTable(idx,k) = 0;
            valueTable(idx,k) = valueTable(idx,k+1);
        elseif valueTable(idx,k+1) > ...
                valueTable(idx-weight(k), k+1) + value(k)
            % it is better to not insert item
            decisionTable(idx,k) = 0;
            valueTable(idx,k) = valueTable(idx,k+1);
        else
            % it is better to insert
            decisionTable(idx,k) = 1;
            valueTable(idx,k) = valueTable(idx-weight(k), k+1) + value(k);
        end
    end % for i
end % for k (items)
% now find the solution, by a forward decision
% process based on state values
X = zeros(numItems,1);
resCapacity = capacity;
for k = 1:numItems
    if decisionTable(resCapacity+1,k) == 1
        X(k) = 1;
        resCapacity = resCapacity - weight(k);
    else
        X(k) = 0;
    end
end
reward = dot(X,value);
end