1
import sys
2
input = sys.stdin.read
3

4
def main():
5
    data = input().strip().split()
6
    index = 0
7
    m = int(data[index])  # 物品数量
8
    index += 1
9
    n = int(data[index])  # 背包容量
10
    index += 1
11

12
    weight = []
13
    for i in range(m):
14
        weight.append(int(data[index]))
15
        index += 1
16

17
    value = []
18
    for i in range(m):
19
        value.append(int(data[index]))
20
        index += 1
21

22
    # dp[i][j] 表示前 i 个物品，容量为 j 时的最大价值
23
    dp = [[0] * (n + 1) for _ in range(m + 1)]
24

25
    for i in range(1, m + 1):
26
        for j in range(n + 1):
27
            if j < weight[i - 1]:
28
                # 容量不足，不能选第 i 个物品
29
                dp[i][j] = dp[i - 1][j]
30
            else:
31
                # 取选与不选两种方案的最大值
32
                dp[i][j] = max(dp[i - 1][j],
33
                               dp[i - 1][j - weight[i - 1]] + value[i - 1])
34

35
    print(dp[m][n])
36

37
main()

1
import sys
2
input = sys.stdin.read
3

4
def main():
5
    data = input().strip().split()
6
    index = 0
7
    m = int(data[index])  # 物品数量
8
    index += 1
9
    n = int(data[index])  # 背包容量
10
    index += 1
11

12
    weight = []
13
    for i in range(m):
14
        weight.append(int(data[index]))
15
        index += 1
16

17
    value = []
18
    for i in range(m):
19
        value.append(int(data[index]))
20
        index += 1
21

22
    # 一维数组优化：dp[j] 表示容量为 j 时的最大价值
23
    dp = [0] * (n + 1)
24

25
    for i in range(m):
26
        # 从后往前遍历，避免覆盖之前的状态
27
        for j in range(n, weight[i] - 1, -1):
28
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
29

30
    print(dp[n])
31

32
main()

1
class Solution:
2
    def canPartition(self, nums: List[int]) -> bool:
3
        total = sum(nums)
4

5
        # 总和为奇数，无法平分
6
        if total % 2 != 0:
7
            return False
8

9
        target = total // 2
10
        n = len(nums)
11

12
        # dp[j] 表示容量为 j 是否可达
13
        dp = [False] * (target + 1)
14
        dp[0] = True  # 容量为 0 一定能构造
15

16
        for i in range(n):
17
            # 从后往前遍历，避免覆盖状态
18
            for j in range(target, nums[i] - 1, -1):
19
                dp[j] = dp[j] or dp[j - nums[i]]
20

21
        return dp[target]