代码随想录算法训练营第三十五天|背包问题 二维 背包问题 一维 46. 携带研究材料 416. 分割等和子集

46. 携带研究材料

46. 携带研究材料（第六期模拟笔试）

代码随想录

思路：这道题是01背包问题的模板题，接下来要讲解一下我对01背包的理解，01背包指的是有限个物品，每个物品只能选或者不选

分为二维背包和一维背包，区别在于dp数组是几维的。

二维背包：dp[i][j]的意思是从编号为0到i的物品中进行选取，总重量不超过j的情况下的最大价值。递推公式分为两种可能，一种是不选择这个新增的，那就是dp[i-1][j]，另一种如果要选择的话，那就要减去其重量并加上其价值，即dp[i-1][j-weight[i]]+value[i]。而初始化的部分，可以先把所有都赋值0，然后在只选择第0个物品的时候，当重量大于等于第0个时，就初始化其的价值。遍历顺序在二维的情况下是无所谓的，在这里我选择第一层循环遍历物品，第二层循环遍历重量。值得一提的是，可以在j<weight[i]时进行剪枝，因为当前的最大重量比新物品的小，不可能引入新的物品，直接等于i-1的情况

n,bag=map(int,input().split())
weight=list(map(int,input().split()))
value=list(map(int,input().split()))
dp=[[0]*(bag+1) for _ in range(n)]

for i in range(weight[0],bag+1):
    dp[0][i]=value[0]

for i in range(n):
    for j in range(bag+1):
        if j<weight[i]:
            dp[i][j]=dp[i-1][j]
        else:
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i])

print(dp[n-1][bag])

一维背包：一维背包舍弃了原来的第一个维度，每一次的更新都在同一层中进行，dp[j]代表总量不超过j的情况下的最大价值。递推公式和之前本质上是一样的，而且可以把之前的剪枝移到j的循环之中。初始化方面，因为初始化和i=0的时候计算是一样的，所以直接全部初始化为0即可。一维背包最需要注意的是遍历的顺序，一定要先物品再重量，而且对重量要从大到小遍历。因为如果从小到大遍历，在更新的时候会多次选取同一个物品（因为原来有i这一维控制，而现在删除掉了，更新的时候会使用i相同的值）。而不能交换遍历顺序的原因也是会导致多次选取同一个物品。

n,bag=map(int,input().split())
weight=list(map(int,input().split()))
value=list(map(int,input().split()))
dp=[0]*(bag+1)

for i in range(n):
    for j in range(bag,weight[i]-1,-1):
        dp[j]=max(dp[j],dp[j-weight[i]]+value[i])

print(dp[bag])

416. 分割等和子集

416. 分割等和子集 - 力扣（LeetCode）

代码随想录

思路：这道题就是01背包的应用，weight和value都是nums数组的值，而判断能否等和就是在于dp[sum/2]是否等于sum/2

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        result=sum(nums)
        if result%2!=0:
            return False
        result//=2
        dp=[0]*(result+1)
        for i in range(len(nums)):
            for j in range(result,nums[i]-1,-1):
                dp[j]=max(dp[j],dp[j-nums[i]]+nums[i])
        if dp[result]==result:
            return True
        else:
            return False