Στον δυναμικό προγραμματισμό γράφουμε έναν αναδρομικό τύπο ο οποίος εκφράζει μεγάλα προβλήματα συνάρτηση μικρότερο και μετά το χρησιμοποιούμε για να συμπληρώσουμε έναν πίνακα με τιμές λύσεων με συνθετικό τρόπο από το μικρότερο από πρόβλημα στο μεγαλύτερο.

Ο τύπος παραμένει επίσης σε έναν αναδρομικό αλγόριθμο αλλά είδαμε προηγουμένως ότι μία απλοϊκή αναδρομή μπορεί να είναι τρομερά αναποτελεσματική επειδή επειδή η ίδια είπε προβλήματα ξανά και ξανά. Τι θα γινόταν αν χρησιμοποιούσαμε μία πιο ευφυή αναδρομική υλοποίηση, μια υλοποίηση οποία θα θυμάται τις προηγούμενες κλήσεις της και επομένως θα απέφευγε την επανάληψή τους;

Στο πρόβλημα του σακιδίου με παραλείψεις ένας τέτοιος αλγόριθμος θα χρησιμοποιούσε έναν πίνακα κατακερματισμού για την αποθήκευση των τιμών Κ(∙) που έχουν ήδη υπολογιστεί. Σε κάθε αναδρομική κλήση η οποία θα ζητούσε κάποιον Κ(w) ο αλγόριθμος θα έλεγχε αν η απάντηση υπάρχει ήδη στον πίνακα και μετά θα προχωρήσει στον υπολογισμό της μόνο αν δεν υπήρχε εκεί. Αυτό το τέχνασμα ονομάζεται υπομνηματισμός ή υπονόμευση (memoization).

Ένας πίνακας κατακερματισμού, αρχικά κενός, περιέχει τιμές του Κ(w) δεικτοδοτημένες κατά w
Συνάρτηση knapsack(w)
if w υπάρχει στον πίνακα κατακερματισμού :return K(w);
K(w)=max{knapsack(w-wi_+vi: wi<=w};
εισαγωγή του Κ(w) στον πίνακα κατακερματισμού, με κλειδί w;
return K(w);

Επειδή αυτός ο αλγόριθμος ποτέ δεν είπα επαναλαμβάνει ένα υπό πρόβλημα, ο χρόνος εκτέλεσης του είναι O(nW) όπως και του δυναμικού προγράμματος. Ωστόσο ο σταθερός παράγοντας σε αυτόν τον συμβολισμό Ο είναι σημαντικά μεγαλύτερος λόγω της επιβάρυνσης από την αναδρομή.

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

Για παράδειγμα υποθέστε ότι το W και όλα τα βάρη wi είναι πολλαπλάσια του 100. Τότε ένα υποπρόγραμμα K(w) είναι άχρηστο εάν το 100 δεν διαιρεί το w. Ο αναδρομικός αλγόριθμος με υπομνηματισμό δεν θα εξετάσει ποτέ αυτές τις άσχετες καταχώρησης πίνακα.