• 任务
  • 01背包（KAMA46）
    • DP思路
    • 滚动数组思路
  • 416. 分割等和子集
    • 思路

任务

有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

01背包（KAMA46）

DP思路

dp[i][j] 为[0,i]的所有物品选取或不选取（在满足重量不超过重量的情况下）在重量j下的可获取的最大价值
不选第i个物品的价值为：dp[i-1][j]
选择第i个物品的价值为：dp[i-1][j-weight[i]]+value[i]
所以递推公式为 dp[i][j] = max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]

# 01背包
n, bagweight = map(int, input().split()) # 物品个数，背包重量
 
weight = list(map(int, input().split())) # 物品重量
value = list(map(int, input().split()))  #物品价值
 
dp = [ [0]*(bagweight+1) for _ in range(n) ] # n行bagweight 列
 
# for j in range(bagweight+1):  # j表示重量
#     if weight[0] <= j: #可以放下
#         dp[0][j] = value[0]
 
for j in range(weight[0],bagweight+1):  # j表示重量
        dp[0][j] = value[0]
 
# for i in range(n): #不用，因为默认全部初始化为0了
#     dp[i][0] = 0
         
for i in range(1,n):
    for j in range(1,bagweight+1):
        if j-weight[i] < 0:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j],dp[i-1][j-weight[i]] + value[i])  #[0,i]的所有物品在重量j下的可获取的最大价值
 
print(dp[n-1][bagweight])

滚动数组思路

即将上面的二维dp数组压缩为一维，关键是如何更新一位数组中的值 ==》 倒序更新，因为实际上只是压缩了空间，实际的思路还是二维的，只不过用一个数组更新，则必须从后往前，因为后面的值要用到前面上面的旧值，如果先更新前面的，就丢失了前面的旧值，从而在计算后面的值时产生错误。这个思路的关键在于不去想一维DP数组的含义，而是去想如何利用一维计算原本需要二维空间的问题

# 01 背包一维（滑动数组）
n, bagweight = map(int, input().split()) # 物品个数，背包重量
 
weight = list(map(int, input().split())) # 物品重量
value = list(map(int, input().split()))  #物品价值
 
dp = [0] * (bagweight+1)
for j in range(weight[0],bagweight+1):
    dp[j] = value[0]
 
for i in range(1,n):
    for j in range(bagweight,0,-1):
        if j-weight[i] >= 0:
            dp[j] =  max(dp[j],dp[j-weight[i]] + value[i]) 
print(dp[bagweight])

416. 分割等和子集

思路

本题还是很难想的.
抽象成背包问题，其中数组中的元素为每个数字多可选1次的物品，其质量和价值均为其值，而背包重量为所需要的target。因为dp[target]为背包在重量为target时的最大价值，当dp[target] == target时，说明找到了数字加起来等于target的元素。
0-1 背包问题求的是最大值，而子集求的是等于某个值，这两个不是一回事啊？但其实是一回事，物品的重量和物品的价值是一样的，所选物品的重量只能小于等于背包重量，因此所选物品的价值也只能小于等于背包的重量，所以求的是所选物品价值的最大值，当物品价值的最大值等于背包重量时，其实也就表示所选物品的重量等于背包价值，也就是找到了子集和等于目标值。
关键是理解dp[i] == i 时，装满重量为i的背包，因为dp[i]表示累计的最大价值，而i表示重量。又因为每个物品的重量等于价值，即我累计了多少价值就选了多少同等重量的物品，所以相等时表示选择某些物体装满背包。所以当dp[target]==target时，表示选择某些数字能够装满背包。

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