Tο πρόβλημα του σακιδίου με επανάληψη

Ας δούμε την εκδοχή του αλγόριθμου του σακιδίου η οποία επιτρέπει επανάληψη. Όπως πάντοτε το κύριο ερώτημα στο δυναμικό προγραμματισμό είναι "ποια είναι τα υπό προβλήματα"; Στη συγκεκριμένη περίπτωση μπορούμε να συρρικνώσουμε με το αρχικό πρόβλημα με δύο τρόπους:

Μπορούμε να εξετάσουμε την περίπτωση σακίδιο μικρότερης χωρητικότητας w<=W, ή την περίπτωση λιγότερων ειδών για παράδειγμα (1,2,...,j, για j<=n). Συνήθως χρειάζεται να πειραματιστούμε για λίγο ώστε να βρούμε ποιος ακριβώς λειτουργεί.
Ο πρώτος προορισμός επιβάλλει μικρότερες χωρητικότητες. Συνακόλουθα ορίζουμε
Κ(w)= η μέγιστη τιμή η οποία επιτυγχάνεται με ένα σακίδιο χωρητικότητας w.

Μπορούμε να εκφράσουμε αυτό τον αριθμό συναρτήσει μικρότερων υπό προβλημάτων; Αν η βέλτιστη λύση του Κ(w) περιλαμβάνει το είδος i, τότε η αφαίρεση αυτού του είδους από το σακίδιο αφήνει μία βέλτιστη λύση για το πρόβλημα  Κ(w-wi). Με άλλα λόγια το Κ(w)είναι απλώς
Κ(w-wi)+vi   για κάποιο i.
Δεν γνωρίζουμε ποιο είναι αυτό το i οπότε θα πρέπει να δοκιμάσουμε όλες τις δυνατότητες
όπου συνήθως η σύμβασή μας είναι  ότι η μέγιστη τιμή ενός κενού συνόλου είναι μηδέν. Τελειώσαμε!
Ο αλγόριθμος τώρα γράφεται μόνος του και είναι  ιδιαίτερα απλός και κομψός.
K(0);
for w=1 toW;
      K(w)=max{K(w-wi)+vi, wi<=w};
return K(W);

Αυτός ο αλγόριθμος συμπληρώνει ένα μονοδιάστατο πίνακα μήκους W+1  από τα αριστερά προς τα δεξιά. Για τον υπολογισμό κάθε καταχώρισης μπορεί να χρειαστεί χρόνος το πολύ Ο(n) οπότε ο συνολικός χρόνος εκτέλεσης είναι O(nW).

Αυτή η συγκεκριμένη παραλλαγή του σχεδίου καταλήγει στην εύρεση της μεγαλύτερης διαδρομής σε ένα γράφο.