携带研究材料

携带研究材料
小明在进行一项研究活动，他需要携带一些研究材料。这些材料有不同的重量和价值。小明的背包有一个最大承重限制，他希望在不超过这个重量限制的情况下，携带尽可能有价值的材料。

给定材料的重量和价值列表，以及背包的最大承重限制，计算小明能够携带的最大价值。

示例 1：

输入：weights = [2, 3, 4, 5], values = [3, 4, 5, 6], capacity = 8
输出：10

解释：小明可以选择重量为3和5的材料，总价值为4 + 6 = 10。
示例 2：

输入：weights = [1, 2, 3], values = [10, 20, 30], capacity = 4
输出：50

解释：小明可以选择重量为1和2的材料，总价值为10 + 20 = 50。

1
2
3
4
5
6
7
8
9
n,bagweight = map(int,input().split())
weights = list(map(int,input().split()))
values = list(map(int,input().split()))
dp = [0]*(bagweight+1)
dp[0] = 0
for i in range(n):
    for j in range(bagweight,weights[i]-1,-1):
        dp[j] = max(dp[j],dp[j-weights[i]]+values[i])
print(dp[bagweight])

分割等和子集

分割等和子集
给你一个 只包含正整数 的 非空 数组 nums 。

请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

示例 1：

输入：nums = [1,5,11,5]

输出：true

解释：数组可以分割成 [1, 5, 5] 和 [11] 。

示例 2：

输入：nums = [1,2,3,5]

输出：false

解释：数组不能分割成两个元素和相等的子集。

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        if sum(nums)%2 != 0:
            return False
        target = sum(nums)//2
        dp = [0]*(target+1)
        dp[0] = 0
        for i in range(len(nums)):
            for j in range(target,nums[i]-1,-1):
                dp[j] = max(dp[j],dp[j-nums[i]]+nums[i])
        return dp[target] == target