function [gewinn,loesung] = rucksack_alles(b,y, b0)

% löst Rucksackproblem mit dynamischer Programmierung
% b - Gewichtsvektor mit Gewicht der Objekte
% y - Vektor mit Werten der Objekte
% b0 - maximale Rucksackkapazitaet

m = numel(b);
F = zeros(b0+1,m+1);
V = zeros(b0+1,m+1); % Vorgaenger zum Merken der Reihenfolge

for k_bar = 1:m
    for b_bar = 1:b(k_bar)
        F(b_bar, k_bar+1) = F(b_bar, k_bar);
        V(b_bar, k_bar+1) = V(b_bar, k_bar);
    end
    
    for b_bar = b(k_bar):b0
        p = F(b_bar+1, k_bar);
        q = F(b_bar-b(k_bar)+1, k_bar+1) + y(k_bar);
        
        if p >= q
            F(b_bar+1,k_bar+1) = p;
            V(b_bar+1,k_bar+1) = V(b_bar+1,k_bar);
        else
            F(b_bar+1,k_bar+1) = q;
            V(b_bar+1,k_bar+1) = k_bar;
        end
    end
end

F
V

b_bar = b0;
k_bar = m;
loesung = [];
while k_bar > 0
    if V(b_bar+1,k_bar+1) == k_bar
        b_bar = b_bar - b(k_bar);
        loesung = [k_bar,loesung];
    else
        k_bar = V(b_bar+1, k_bar+1);
    end
end

gewinn = F(b0+1,m+1);