def knapsack_01(weights, values, capacity):
    """
    0-1背包问题
    :param weights: 物品重量列表
    :param values: 物品价值列表
    :param capacity: 背包容量
    :return: 最大价值
    """
    n = len(weights)
    
    # 创建DP表，dp[i][w]表示前i个物品、容量为w时的最大价值
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):  # 遍历物品
        for w in range(capacity + 1):  # 遍历容量
            # 情况1：不选第i个物品
            dp[i][w] = dp[i-1][w]
            
            # 情况2：选第i个物品（如果容量足够）
            if w >= weights[i-1]:
                # 注意：values和weights是0-indexed，所以用i-1
                choose = dp[i-1][w - weights[i-1]] + values[i-1]
                dp[i][w] = max(dp[i][w], choose)
    
    return dp[n][capacity]

# 测试
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 8
print("0-1背包最大价值:", knapsack_01(weights, values, capacity))  # 输出: 10

def knapsack_unbounded(weights, values, capacity):
    """
    完全背包问题（每个物品可选无限次）
    :param weights: 物品重量列表
    :param values: 物品价值列表  
    :param capacity: 背包容量
    :return: 最大价值
    """
    n = len(weights)
    
    # 优化：只需要一维数组
    dp = [0] * (capacity + 1)
    
    for i in range(n):  # 遍历物品
        for w in range(weights[i], capacity + 1):  # 从小到大遍历容量
            # 状态转移：选第i个物品
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    
    return dp[capacity]

# 测试
print("完全背包最大价值:", knapsack_unbounded(weights, values, capacity))  # 输出: 12

def subset_sum(nums, target):
    """
    判断是否存在子集，使其和等于目标值
    :param nums: 数字列表
    :param target: 目标和
    :return: 是否存在这样的子集
    """
    # dp[i][j]表示：使用前i个数字，能否组成和为j
    n = len(nums)
    dp = [[False] * (target + 1) for _ in range(n + 1)]
    
    # 初始化：不选任何数字时，和为0是可行的
    for i in range(n + 1):
        dp[i][0] = True
    
    for i in range(1, n + 1):
        for j in range(1, target + 1):
            # 不选第i个数字
            dp[i][j] = dp[i-1][j]
            
            # 选第i个数字（如果j >= nums[i-1]）
            if j >= nums[i-1] and dp[i-1][j - nums[i-1]]:
                dp[i][j] = True
    
    return dp[n][target]

# 测试
nums = [3, 34, 4, 12, 5, 2]
target = 9
print(f"是否存在和为{target}的子集:", subset_sum(nums, target))  # 输出: True (4+5)