def knapsack_01(values, weights, capacity):
    n = len(values)
    dp = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)]
    for i in range(1, n + 1):
        for w in range(1, capacity + 1):
            if weights[i - 1] <= w:
                dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1])
            else:
                dp[i][w] = dp[i - 1][w]
    return dp[n][capacity]
 
 
# 测试数据
values = [60, 100, 120]
weights = [10, 20, 30]
capacity = 50
result = knapsack_01(values, weights, capacity)
print(result)
 
 

ZGVmIGtuYXBzYWNrXzAxKHZhbHVlcywgd2VpZ2h0cywgY2FwYWNpdHkpOgogICAgbiA9IGxlbih2YWx1ZXMpCiAgICBkcCA9IFtbMCBmb3IgXyBpbiByYW5nZShjYXBhY2l0eSArIDEpXSBmb3IgXyBpbiByYW5nZShuICsgMSldCiAgICBmb3IgaSBpbiByYW5nZSgxLCBuICsgMSk6CiAgICAgICAgZm9yIHcgaW4gcmFuZ2UoMSwgY2FwYWNpdHkgKyAxKToKICAgICAgICAgICAgaWYgd2VpZ2h0c1tpIC0gMV0gPD0gdzoKICAgICAgICAgICAgICAgIGRwW2ldW3ddID0gbWF4KGRwW2kgLSAxXVt3XSwgZHBbaSAtIDFdW3cgLSB3ZWlnaHRzW2kgLSAxXV0gKyB2YWx1ZXNbaSAtIDFdKQogICAgICAgICAgICBlbHNlOgogICAgICAgICAgICAgICAgZHBbaV1bd10gPSBkcFtpIC0gMV1bd10KICAgIHJldHVybiBkcFtuXVtjYXBhY2l0eV0KCgojIOa1i+ivleaVsOaNrgp2YWx1ZXMgPSBbNjAsIDEwMCwgMTIwXQp3ZWlnaHRzID0gWzEwLCAyMCwgMzBdCmNhcGFjaXR5ID0gNTAKcmVzdWx0ID0ga25hcHNhY2tfMDEodmFsdWVzLCB3ZWlnaHRzLCBjYXBhY2l0eSkKcHJpbnQocmVzdWx0KQoK