7 背包问题

E420: 01背包问题简单

dp, https://sunnywhy.com/sfbj/11/7/420

有 n 件物品，每件物品的重量为 wi，价值为 ci。现在需要选出若干件物品放入一个容量为 V 的背包中（每件物品至多选一次），使得在选入背包的物品重量之和不超过容量 V 的前提下，让背包中物品的价值之和最大，求最大价值。

输入描述

第一行两个整数 n、V（1 ≤ n ≤ 100，1 ≤ V ≤ 10^3），分别表示物品数量、背包容量；

第二行为用空格隔开的个整数 wi（1 ≤ wi ≤ 10），表示物品重量；

第三行为用空格隔开的个整数 ci（1 ≤ ci ≤ 10），表示物品价值。

输出描述

输出一个整数，表示最大价值。

样例1

输入

5 8
3 5 1 2 2
4 5 2 1 3

输出

解释

假设物品编号为从1到5，那么选择第1、3、4、5件物品时，物品重量值和为 3+1+2+2=8，此时的价值是 4+2+1+3=10，是最大价值。

这是一个经典的 01 背包问题，我们可以使用 动态规划（DP） 来解决。

解题思路

定义 dp[j] 表示容量为 j 的背包所能装下的最大价值。
初始时 dp[0...V] = 0。
对于每一件物品 i（重量 w[i]，价值 c[i]），我们从后往前更新 dp 数组（避免重复选择）：
python
```
for j in range(V, w[i] - 1, -1):
    dp[j] = max(dp[j], dp[j - w[i]] + c[i])
```

Python 代码实现

python

# 读取输入
n, V = map(int, input().split())
w = list(map(int, input().split()))
c = list(map(int, input().split()))

# 初始化 dp 数组
dp = [0] * (V + 1)

# 动态规划填表
for i in range(n):
    # 从后往前遍历容量，防止重复选取
    for j in range(V, w[i] - 1, -1):
        dp[j] = max(dp[j], dp[j - w[i]] + c[i])

# 输出最大价值
print(dp[V])

该算法时间复杂度为 O(n × V)，空间复杂度为 O(V)，完全满足题目限制（n ≤ 100，V ≤ 1000）。

M421: 01背包问题的最优方案

https://sunnywhy.com/sfbj/11/7/421

有 n 件物品（假设编号为从1到n），每件物品的重量为 wi，价值为 ci。现在需要选出若干件物品放入一个容量为的背包中（每件物品至多选一次），使得在选入背包的物品重量之和不超过容量 V 的前提下，让背包中物品的价值之和最大，求最大价值与对应的最优方案。

输入描述

第一行两个整数 n、V（1 ≤ n ≤ 100，1 ≤ V ≤ 10^3），分别表示物品数量、背包容量；

第二行为用空格隔开的 n 个整数 wi（1 ≤ wi ≤ 10），表示物品重量；

第三行为用空格隔开的个整数 ci（1 ≤ ci ≤ 10），表示物品价值。

输出描述

第一行输出一个整数，表示最大价值。

第二行输出若干个整数，按升序给出选择的物品编号。整数之间用空格隔开，行末不允许有多余的空格。

如果有多种最优方案，那么输出物品编号字典序最小的一种，即如果有两个物品编号序列 A(a1, a2, ...) 与 B(b1, b2, ...)，满足 a1 == b1, a2 == b2, ..., ak == bk, $a_{k + 1} < b_{k + 1}$ ，那么把物品序列 A 优先输出。

样例1

输入

5 8
3 5 1 2 2
4 5 2 1 3

输出

10
1 3 4 5

解释

假设物品编号为从1到5，那么选择第1、3、4、5件物品时，物品重量值和为 3+1+2+2=8，此时的价值是 4+2+1+3=10，是最大价值。

这是一个经典的 0/1 背包问题，但增加了一个难点：需要输出字典序最小的最优方案。

核心思路

求最大价值 (标准 DP)：使用动态规划求解。定义 dp[i][j] 表示从第 i 个物品到第 n 个物品中选择，容量为 j 时能获得的最大价值。
- 注意顺序：通常求最大价值时，我们会从第 1 个物品遍历到第 n 个物品。但是，为了方便在第二步输出“字典序最小”的方案，我们需要逆序遍历物品（从第 n 个到第 1 个）。
- 状态转移方程： $d p [i] [j] = max (d p [i + 1] [j], d p [i + 1] [j - w [i]] + c [i])$ 其中 $w [i]$ 是重量， $c [i]$ 是价值。
求最优方案 (路径还原)：既然我们要输出字典序最小的方案（即优先选编号小的物品），我们从第 1 个物品开始正向遍历到第 n 个物品：
- 如果 j >= w[i]（容量足够）且 dp[i][j] == dp[i+1][j-w[i]] + c[i]，说明选择了物品 i 可以达到最优解。由于我们要求字典序最小，只要能选，就立刻选它（贪心策略），然后容量减去 w[i]，继续判断下一个物品。
- 如果选了它不能达到最优解（即上述等式不成立），则跳过该物品。

为什么需要逆序 DP？

如果我们正序 DP（dp[1]...dp[n]），在回溯找路径时，我们通常是从 dp[n] 往回推到 dp[1]。这样确定的路径是倒着确定的（例如先确定选不选物品 5，再确定选不选物品 4...）。这很难保证“优先选编号 1”这个字典序要求。 逆序 DP 后，dp[1][V] 存储的是从 1 到 n 选取的最大价值。我们在回溯时，就可以从物品 1 开始判断：只要物品 1 能贡献于最大价值，我们就必选它，这样自然满足了“字典序最小”的要求。

Python 代码实现

python

import sys

def solve():
    # 读取输入
    # sys.stdin.read().split() 可以一次性读取所有空白分隔的 token，处理多行输入很方便
    input_data = sys.stdin.read().split()
    
    if not input_data:
        return

    iterator = iter(input_data)
    
    try:
        n = int(next(iterator))
        V = int(next(iterator))
        
        # 读取重量，注意题目编号是从1开始，我们为了方便处理，可以在列表前加个0占位
        # 或者在逻辑上自行调整下标。这里选择由 0 占位，让 weights[1] 对应物品 1
        weights = [0] * (n + 1)
        values = [0] * (n + 1)
        
        for i in range(1, n + 1):
            weights[i] = int(next(iterator))
            
        for i in range(1, n + 1):
            values[i] = int(next(iterator))
            
    except StopIteration:
        return

    # 初始化 DP 表
    # dp[i][j] 表示从第 i 个物品到第 n 个物品，背包容量为 j 时的最大价值
    # 大小为 (n+2) * (V+1)，多一行防止越界，初始全为 0
    dp = [[0] * (V + 1) for _ in range(n + 2)]

    # 1. 逆序进行动态规划
    for i in range(n, 0, -1):
        for j in range(V + 1):
            # 策略1: 不选第 i 个物品
            dp[i][j] = dp[i + 1][j]
            
            # 策略2: 选第 i 个物品 (前提是装得下)
            if j >= weights[i]:
                val_with_item = dp[i + 1][j - weights[i]] + values[i]
                if val_with_item > dp[i][j]:
                    dp[i][j] = val_with_item
    
    # 输出最大价值
    max_val = dp[1][V]
    print(max_val)

    # 2. 正向还原路径，寻找字典序最小的方案
    current_capacity = V
    chosen_items = []
    
    for i in range(1, n + 1):
        # 如果当前容量装不下，肯定不选，直接看下一个
        if current_capacity < weights[i]:
            continue
            
        # 核心判断：
        # 如果 dp[i][current_capacity] 的值等于 "选了物品i后的剩余价值 + 物品i的价值"
        # 说明选物品 i 是最优策略之一。为了字典序最小，我们必须选它。
        # 注意：这里实际上是利用了 dp 表的性质。dp[i][v] 是最优解，
        # dp[i+1][v-w[i]] + val[i] 也是如果选了i之后的最优解。
        # 如果两者相等，说明选 i 没毛病。
        if dp[i][current_capacity] == dp[i + 1][current_capacity - weights[i]] + values[i]:
            chosen_items.append(str(i))
            current_capacity -= weights[i] # 容量减小
            
            # 优化：如果容量为0或者价值找齐了，其实可以提前结束，
            # 但为了逻辑简单，继续循环也无妨（后续判断不会进）。
            
    # 输出方案，按空格分隔
    print(" ".join(chosen_items))

if __name__ == "__main__":
    solve()

代码详解与样例测试

样例输入：

5 8
3 5 1 2 2
4 5 2 1 3

执行流程：

DP 构建 (逆序)：我们从物品 5 开始填表，一直填到物品 1。 dp[1][8] 最终会存储最大价值。根据计算，dp[1][8] 的结果是 10。
路径还原 (正序)：初始 current_capacity = 8。
- 物品 1 (w=3, v=4): 检查 dp[1][8] 是否等于 dp[2][8-3] + 4?
  - dp[2][5] 经过计算是 6 (选3,4,5中的某些)。
  - 6 + 4 = 10。
  - 相等！为了字典序最小，选物品 1。
  - 剩余容量 8 - 3 = 5。
- 物品 2 (w=5, v=5): 检查 dp[2][5] 是否等于 dp[3][5-5] + 5?
  - dp[3][0] 是 0。
  - 0 + 5 = 5。
  - 但是 dp[2][5] 实际值是 6 (选3,5 => 2+3=5? 不对，最优是选3,4,5组合里的)。
  - 其实在逆序DP时，dp[2][5]（从2,3,4,5中选，容5）的最优解是选物品 3, 4, 5 (w=1+2+2=5, v=2+1+3=6)。
  - 如果不选物品2，价值是 dp[3][5] = 6。
  - 如果选物品2，价值是 dp[3][0] + 5 = 5。
  - 6 > 5，所以最优解一定是不选物品 2。
  - 不选物品 2。
- 物品 3 (w=1, v=2): 检查 dp[3][5] 是否等于 dp[4][5-1] + 2?
  - dp[3][5] 是 6。
  - dp[4][4] (从4,5选，容4) 最优是选 4, 5 (w=2+2=4, v=1+3=4)。Wait, checking math...
  - 实际上 dp[4][4] 是 4 (选物品4和5)。4 + 2 = 6。
  - 相等！选物品 3。
  - 剩余容量 5 - 1 = 4。
- 物品 4 (w=2, v=1): 检查 dp[4][4] 是否等于 dp[5][4-2] + 1?
  - dp[4][4] 是 4。
  - dp[5][2] (从5选，容2) 是 3 (选物品5)。
  - 3 + 1 = 4。
  - 相等！选物品 4。
  - 剩余容量 4 - 2 = 2。
- 物品 5 (w=2, v=3): 检查 dp[5][2] 是否等于 dp[6][0] + 3?
  - dp[5][2] 是 3。
  - dp[6][0] 是 0。
  - 0 + 3 = 3。
  - 相等！选物品 5。
  - 剩余容量 2 - 2 = 0。

最终输出：

10
1 3 4 5

这与样例输出一致。

复杂度分析

时间复杂度： $O (n \times V)$ 。因为要填充 DP 表。
空间复杂度： $O (n \times V)$ 。需要二维数组存储 DP 状态以便回溯路径。（如果是只需要最大价值，空间可以优化到 $O (V)$ ，但为了输出具体方案，通常保留二维数组最简单直观）。

7 背包问题 ​

E420: 01背包问题 简单 ​

M421: 01背包问题的最优方案 ​

7 背包问题

E420: 01背包问题简单

M421: 01背包问题的最优方案