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

2021/11/13 12:10:09

本文主要是介绍阿良的算法之路(动态规划之分组背包问题),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题目描述

参考题解

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])



这篇关于阿良的算法之路(动态规划之分组背包问题)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程