题解 | #【模板】01背包#

# 状态定义：dp1[i]表示不考虑背包是否装满，在容量为i的情况下，最多装多大价值的物品。
# 状态转移：遍历所有的物品，要么选择当前物品，要么不选，取价值最大的，并且通过这种方式跟新所有情况的状态。即
# dp1[j]=Math.max(dp1[j−v[i]]+w[i],dp1[j])


# 状态定义：dp2[i]表示背包恰好装满时，在容量为i的情况下，最多装多大价值的物品。
# 状态初始化：将背包容量为0的情况设置价值为0，其它情况设置为最小的Integer型整数，表示不可达状态。后续所有的状态都需要从为0的状态转移过去。
# 状态转移：遍历所有的物品，要么选择当前物品，要么不选，取价值最大的，并且通过这种方式跟新所有情况的状态。即
# dp2[j]=Math.max(dp2[j−v[i]]+w[i],dp2[j])。

class Solution:

    def slove(self, V: int, vlist: List[int], wlist: List[int]) -> (int, int):
        dp1 = [float('-inf') for _ in range(V+1)] 
        dp1[0] = 0  
        for ind in range(len(vlist)):     
            for vv in range(V, vlist[ind]-1, -1):
                dp1[vv] = max(dp1[vv], dp1[vv - vlist[ind]] + wlist[ind])
        
        dp1[V] = max(dp1[V], 0)
        return max(dp1), dp1[V]


if __name__ == '__main__':
    message = input()
    messagesplt = message.split(" ")
    n = int(messagesplt[0])
    v = int(messagesplt[1])

    vlist = []
    wlist = []
    for _ in range(n):
        message = input()
        messagesplt = message.split(" ")
        vlist.append(int(messagesplt[0]))
        wlist.append(int(messagesplt[1]))
    
    solution = Solution()
    result = solution.slove(v, vlist, wlist)
    print(result[0])
    print(result[1])