ここでは、 「同じ品物を何度も選ぶことができる」という制約条件のもとでのナップサック問題について、 DP(動的計画法)を使用し python3 で実装する方法を紹介します。
また 「プログラミングコンテストチャレンジブック（第2版）」（通称：蟻本）の p58 を例にしています。
時間計算量は、O(nW)です。
# 入力
n = 3
w = [3, 4, 2]
v = [4, 5, 3]
W = 7
#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+1][j - w[i]] + v[i])
print(dp[n][W])
if __name__ == '__main__':
solve()