阿良的算法之路(动态规划之分组背包问题)

题目描述

阿良的算法之路(动态规划之分组背包问题)

参考题解

if __name__ == "__main__":
    N, V = map(int, input().split())
    v = []
    w = []
    s = []
    dp = [0] * (V + 1)
    for i in range(N):
        s.append(int(input()))
        tv = []
        tw = []
        for j in range(s[i]):
            a, b = map(int, input().split())
            tv.append(a)
            tw.append(b)
        v.append(tv)
        w.append(tw)
        
    for i in range(N):
        for j in range(V, 0- 1, -1):
            for k in range(s[i]):
                if j >= v[i][k]:
                    dp[j] = max(dp[j],dp[j-v[i][k]]+w[i][k])
    print(dp[V])

上一篇:c#-List<T>的Add()和Append()的区别


下一篇:StringBuilder类