ここでは、ナップサック問題について、 「プログラミングコンテストチャレンジブック（第2版）」（通称：蟻本）の p55 を例に、python3 で実装する方法を紹介します。
DP(動的計画法)を使用し、配列を昇順で更新していく方法で記述します。
また、時間計算量は、O(nW)です。
# 入力
n = 4
w = [2, 1, 3, 2]
v = [3, 2, 4, 2]
W = 5
#DPテーブル(0 で初期化)
dp = [ [0 for i in range(W+1)] for j in range(n+1)]
def solve():
for i in range(n):
for j in range(W+1):
#品物は入らない
if j < w[i]:
dp[i+1][j] = dp[i][j]
#入れない場合と入れる場合の大きい方をとる
else:
dp[i+1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i])
print(dp[n][W])
if __name__ == '__main__':
solve()