ここでは、ナップサック問題について、 「プログラミングコンテストチャレンジブック（第2版）」（通称：蟻本）の p53 を例に、python3 で実装する方法を紹介します。
　時間計算量は、O(nW) です。

# 入力
n = 4
w = [2, 1, 3, 2]
v = [3, 2, 4, 2]
W = 5
#メモ化テーブル(-1 で初期化)
dp = [ [-1 for i in range(W+1)] for j in range(n+1)]

# i番目以降の品物から重さの総和が j 以下となるように選ぶ
def rec(i, j):
    if dp[i][j] >= 0:
        #すでに調べたことがあるならばその結果を再利用
        return dp[i][j]
    if i == n:
        #もう品物は残っていない
        res = 0
    elif j < w[i]:
        #この品物は入らない
        res = rec(i+1, j)
    else:
        #入れない場合と入れる場合を両方試す
        res = max(rec(i+1, j), rec(i+1, j-w[i]) + v[i])
    dp[i][j] = res
    return dp[i][j]
    

if __name__ == '__main__':
    print(rec(0, W))