2025-01-21发表2025-02-10更新算法21 分钟读完 (大约3137个字)0次访问

背包问题

计算机科学、算法设计和优化理论中非常著名的“背包问题”（Knapsack Problem）是一个典型的组合优化问题，也是动态规划算法的一个经典应用。
背包问题有多种变体，但最基本的形式是：
给定一组物品，每种物品都有自己的重量和价值，在限定的总重量内，如何选择装入背包的物品，使得背包内物品的总价值最大。

0-1背包

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

暴力解法应该是怎么样的呢？
每一件物品其实只有两个状态，取或者不取，所以可以使用回溯法搜索出所有的情况，那么时间复杂度就是O(2^n)，这里的n表示物品数量。
背包最大重量为4。
物品为：

物品	重量	价值
0	1	15
1	3	20
2	4	30

问背包能背的物品最大价值是多少？
确定dp数组以及下标的含义：
需要使用二维数组，为什么呢？因为有两个维度需要表示，分别是：物品和背包容量

那么这里 i,j,dp[i][j] 分别表示什么呢？
i 来表示物品、j表示背包容量。
dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。
确定递推公式
对于递推公式，首先我们要明确有哪些方向可以推导出 dp[i][j]。
不放物品i：由dp[i - 1][j]推出，此时dp[i][j]就是dp[i - 1][j]。
放物品i：由dp[i - 1][j - weight[i]]推出，dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最大价值，那么dp[i - 1][j - weight[i]] + value[i] （物品i的价值），就是背包放物品i得到的最大价值

递归公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])
dp数组如何初始化
关于初始化，一定要和dp数组的定义吻合，否则到递推公式的时候就会越来越乱。
首先从dp[i][j]的定义出发，如果背包容量j为0的话，即dp[i][0]，无论是选取哪些物品，背包价值总和一定为0。
再看状态转移方程 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); 可以看出i 是由 i-1 推导出来，那么i为0的时候就一定要初始化。
dp[0][j]，即：i为0，存放编号0的物品的时候，各个容量的背包所能存放的最大价值。
那么很明显当 j < weight[0]的时候，dp[0][j]应该是 0，因为背包容量比编号0的物品重量还小。
当j >= weight[0]时，dp[0][j] 应该是value[0]，因为背包容量放足够放编号0物品。

确定遍历顺序
有两个遍历的维度：物品与背包重量
这里降维会逆序，要理解
举例推导dp数组

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

二维dp代码如下：

def fun(n, weights, vals):
    nums, bag = n[0], n[1]
    # dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少
    dp = [[0] * (bag + 1) for _ in range(nums)]
    # 背包容量j为0的话，即dp[i][0] = 0
    # dp[0][j]，即：i为0，存放编号0的物品的时候，各个容量的背包所能存放的最大价值
    for j in range(weights[0], bag + 1):
        print(j)
        dp[0][j] = vals[0]

    print(dp)

    # dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])
    for i in range(1, nums):
        for j in range(bag + 1):
            if j < weights[i]:
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weights[i]] + vals[i])
    print(dp)
    return dp[-1][-1]


if __name__ == '__main__':
    # n, weight, vals = ([int(x) for x in input().split()],
    #                    [int(x) for x in input().split()],
    #                    [int(x) for x in input().split()])
    n = [6, 1]
    weights = [2, 2, 3, 1, 5, 2]
    vals = [2, 3, 1, 5, 4, 3]
    print(fun(n, weights, vals))  # 5

优化成一维dp：
其实可以发现如果把dp[i - 1]那一层拷贝到dp[i]上，表达式完全可以是：dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i]);
与其把dp[i - 1]这一层拷贝到dp[i]上，不如只用一个一维数组了，只用dp[j]（一维数组，也可以理解是一个滚动数组）。即dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
这就是滚动数组的由来，需要满足的条件是上一层可以重复利用，直接拷贝到当前层。
二维dp遍历的时候，背包容量是从小到大，而一维dp遍历的时候，背包是从大到小。

为什么呢？
倒序遍历是为了保证物品i只被放入一次！如果一旦正序遍历了，那么物品0就会被重复加入多次！

# https://kamacoder.com/problempage.php?pid=1046
def fun():
    n, weight, vals = ([int(x) for x in input().split()],
                       [int(x) for x in input().split()],
                       [int(x) for x in input().split()])

    nums, bag = n[0], n[1]
    dp = [0] * (bag + 1)
    for j in range(weight[0], bag + 1):
        dp[j] = vals[0]
    for i in range(1, nums):
        for j in range(bag, weight[i] - 1, -1):
            dp[j] = max(dp[j], dp[j - weight[i]] + vals[i])
    return dp[bag]


if __name__ == '__main__':
    print(fun())

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

当做01背包做，总容量是已知的
当某个dp达到target后，就填满了背包
执行用时分布1993ms，击败26.68%
消耗内存分布38.73MB，击败5.89%

class Solution(object):
    def canPartition(self, nums): # 1 - 100
        total = sum(nums)
        if total % 2:
            return False

        target = total // 2
        length = len(nums)
        # 总容量是target
        # 重量和价值都是num
        # 背包满时即为一个子集
        # 另一个是剩下的就行
        dp = [[0] * (target + 1) for _ in range(length)]  # dp[i][j]表示背包容量为j时从0-i中任取所得到的最大总和
        # dp[0][j] 表示背包容量为j时从0中任取所得到的最大总和
        for j in range(nums[0], target + 1):
            dp[0][j] = nums[0]

        for i in range(1, length):
            for j in range(target + 1):
                if j < nums[i]:
                    dp[i][j] = dp[i - 1][j]
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - nums[i]] + nums[i])
                if dp[i][j] == target:
                    return True
        return False

降维：
这里可以思考下为什么遍历变成倒序了
依旧正序是错误的，127 / 143 个通过的测试用例

class Solution(object):
    def canPartition(self, nums): # 1 - 100
        total = sum(nums)
        if total % 2:
            return False

        target = total // 2
        length = len(nums)
        dp = [0] * (target + 1)  # dp[j]表示背包容量为j时从0-i中任取所得到的最大总和，i被降维了，滚动数组
        # dp[j] 表示背包容量为j时从0中任取所得到的最大总和
        for j in range(nums[0], target + 1):
            dp[j] = nums[0]

        for i in range(1, length):
            for j in range(target + 1):
                if j < nums[i]:
                    dp[j] = dp[j]
                else:
                    dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])
                if dp[j] == target:
                    return True
        return False

如果使用一维dp数组，物品遍历的for循环放在外层，遍历背包的for循环放在内层，且内层for循环倒序遍历！
倒序后：
执行用时分布1518ms，击败71.56%
消耗内存分布12.13MB，击败51.08%

class Solution(object):
    def canPartition(self, nums): # 1 - 100
        total = sum(nums)
        if total % 2:
            return False

        target = total // 2
        length = len(nums)
        dp = [0] * (target + 1)
        for j in range(nums[0], target + 1):
            dp[j] = nums[0]

        for i in range(1, length):
            for j in range(target, -1, -1):
                if j < nums[i]:
                    dp[j] = dp[j]
                else:
                    dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])
                if dp[j] == target:
                    return True
        return False

去掉了没有变化的dp[j] = dp[j]
执行用时分布1579ms，击败70.24%
消耗内存分布11.97MB，击败76.67%

class Solution(object):
    def canPartition(self, nums): # 1 - 100
        total = sum(nums)
        if total % 2:
            return False

        target = total // 2
        length = len(nums)
        dp = [0] * (target + 1)
        for j in range(nums[0], target + 1):
            dp[j] = nums[0]

        for i in range(1, length):
            for j in range(target, -1, -1):
                if j >= nums[i]:
                    dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])
                if dp[j] == target:
                    return True
        return False

1046. 最后一块石头的重量 - 力扣（LeetCode）

用堆做

class Solution(object):
    def lastStoneWeight(self, stones):
        hq = []

        for s in stones:
            heapq.heappush(hq, -s)

        while hq:
            v1 = -heapq.heappop(hq)
            if not hq:
                return v1

            v2 = -heapq.heappop(hq)
            if v1 != v2:
                heapq.heappush(hq, -abs(v1 - v2))

        return 0

执行用时分布15ms，击败63.38%
消耗内存分布11.46MB，击败43.66%
v1 v2的大小关系是已知的，没必要用绝对值abs()
以及堆的初始化可以更简单

class Solution(object):
    def lastStoneWeight(self, stones):
        hq = [-s for s in stones]
        heapq.heapify(hq)

        while hq:
            v1 = -heapq.heappop(hq)
            if not hq:
                return v1

            v2 = -heapq.heappop(hq)
            if v1 != v2:
                heapq.heappush(hq, v2 - v1)

        return 0

1049. 最后一块石头的重量 II - 力扣（LeetCode）

提示：

把最终的答案看作是权重的总和，每个权重前面都有+或-符号。实际上，每个符号的和都是1。
使用动态规划:对于每一个可能的和N颗石头，这些和+x或-x可能与N+1颗石头，其中x是最新的石头的值。(这将多算全部为正或全部为负的总和，但这些都无关紧要。)

和分割子集完全一个思路捏
执行用时分布34ms，击败53.47%
消耗内存分布11.39MB，击败86.12%

class Solution(object):
    def lastStoneWeightII(self, stones):
        total = sum(stones)
        target = total // 2
        # 总容量是target
        # 重量和价值都是stone
        dp = [0] * (target + 1)  # dp[j]表示背包容量为j时从0-i中任取所得到的最大总和，i被降维了，滚动数组
        # dp[j] 表示背包容量为j时从0中任取所得到的最大总和
        for j in range(stones[0], target + 1):
            dp[j] = stones[0]

        for i in range(1, len(stones)):
            for j in range(target, -1, -1):
                if j >= stones[i]:
                    dp[j] = max(dp[j], dp[j - stones[i]] + stones[i])

        # print(dp)
        return total - 2 * dp[-1]

494. 目标和 - 力扣（LeetCode）

可以回溯法硬解，但为什么它也可以是背包？
首先，确实对于每一个num都有两种选择，取正或负
dp = [0] * (m + 1) 和 dp[0] = 1：
创建一个长度为 m + 1 的列表 dp，用于存储不同和值的组合数。
初始化 dp[0] 为 1，表示空集的和为 0，只有一种方法。
两层循环：
外层循环遍历数组 nums 中的每个元素。
内层循环从 m 倒序遍历到 0。
如果当前和值 j 大于等于当前数组元素 nums[i]，说明可以选择当前元素加入子集中，此时 dp[j] 的值等于不选择当前元素的组合数（即 dp[j]）加上选择当前元素的组合数（即 dp[j - nums[i]]）。
执行用时分布39ms，击败77.99%
消耗内存分布11.30MB，击败95.60%

474. 一和零 - 力扣（LeetCode）

执行用时分布1586ms，击败65.91%
消耗内存分布11.55MB，击败74.93%
01背包，但是物品重量有两个维度

class Solution(object):
    def findMaxForm(self, strs, m, n):  # m个0, n个1
        dp = [[0] * (n + 1) for _ in range(m + 1)]  # dp[i][j]表示有i个0，j个1的满足条件的最大组合数

        for s in strs:
            c0 = s.count('0')
            c1 = len(s) - c0
            print("c0", c0, "c1", c1)
            for i in range(m, c0 - 1, -1):
                for j in range(n, c1 - 1, -1):
                    dp[i][j] = max(dp[i][j], dp[i - c0][j - c1] + 1)

        print(dp)
        return dp[-1][-1]

完全背包问题

问题描述：与0-1背包问题类似，但每种物品的数量是无限的。
解法：同样使用动态规划，但状态转移方程有所不同。由于每种物品可以无限次使用，因此在更新dp[i][j]时，需要考虑从dp[i-1][j]（不选第i个物品）和dp[i][j-wt[i]]+val[i]（选择第i个物品，且假设之前已经选择了足够的空间来放下它）中选择较大的值。

多重背包问题

每种物品有一定数量的限制。

分组背包问题

物品被划分为若干组，每组中的物品互斥（即每组中最多只能选一个物品），求解最优解。
二维背包问题：除了重量和价值外，还考虑了其他维度的限制（如体积、时间等）。

记忆中的背包 - BZOJ 4971 - Virtual Judge

构造

背包问题

https://sonder10110.github.io/算法/bag/

作者

sonder

发布于

2025-01-21

更新于

2025-02-10

背包问题

0-1背包

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

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

1046. 最后一块石头的重量 - 力扣（LeetCode）

1049. 最后一块石头的重量 II - 力扣（LeetCode）

494. 目标和 - 力扣（LeetCode）

474. 一和零 - 力扣（LeetCode）

完全背包问题

多重背包问题

分组背包问题

作者

发布于

更新于

许可协议

目录

最新文章

归档

标签