题目描述

01背包问题

算法

dynamic programming

时间复杂度分析：O(NV)

python 代码

import sys
k = 0
v = [0 for i in range(1001)]
w = [0 for j in range(1001)]
for line in sys.stdin:
    if k==0:
        N, V = map(int, line.split())
    else:
        v[k], w[k] = map(int, line.split())
    k += 1

dp = [[0 for j in range(V+1) ] for i in range(N+1)] 
for i in range(N+1):
    for j in range(V+1):
        if j-v[i]>=0:
            dp[i][j] = max(dp[i-1][j-v[i]]+w[i], dp[i-1][j])
        else:
            dp[i][j] = dp[i-1][j]

print dp[N][V]