page背包问题(动态规划)

发表于 更新于 分类于 阅读次数： 本文字数： 2k 阅读时长 ≈ 5 分钟

背包问题 （动态规划）

(一) 背包问题学习大纲

  1. 基础概念
    a. [什么是背包问题](#什么是背包问题 ?)
    b. 背包问题的基本形式

  2. 背包问题的主要类型
    a. 0-1背包问题：每个物品要么选要么不选（不能分割）
    b. 完全背包问题：每个物品可以选无限次
    c. 多重背包问题：每个物品有数量限制
    d. 混合背包问题
    e. 二维费用背包问题
    f. 分组背包问题：物品分组，每组只能选一个
    g.背包问题求方案数
    h.求背包问题的方案
    i.有依赖的背包问题

  3. 解法技术

  4. 优化技巧

  5. 扩展应用

(二) 正文

什么是背包问题 ？

背包问题(Knapsack Problem)是组合优化中的一个经典问题
,核心思想是——在有限的资源约束下，如何选择物品的组合，来实现目标
限通常描述如下：
给定一个容量为 W 的背包, 以及 n个物品, 每个物品 i 有:

  • 一个重量 wi （weight）
  • 一个价值 vi（value）
    目标：选择若干物品装入背包，使得总重量不超过 W ，且总价值最大。

如何理解资源分配的抽象模型？
背包问题本质是资源受限下的最优策问题，其核心要素可映射到广泛场景

  • 背包容量 -> 资源上线（预算、时间、空间）
  • 物品 -> 待分配的任务、项目、货物等。
  • 价值与重量 -> 收益与成本（利润与投入 、 重要性与耗时）。

背包问题的基本形式

0-1背包问题

问题描述

有N件物品和一个容量为V的背包。第i件物品的重量是w[i]，价值是v[i]。求解将哪些物品装入背包可使这些物品的总重量不超过背包容量，且总价值最大。

解决思路

  1. 暴力解法（理解问题）
    最直观的方法就是尝试所有可能的组合，计算每种组合的总重量和价值，然后找出满足重量限制的最大价值组合。但这种方法时间复杂度是O(2^n^) ，当n较大时不可行

  2. 动态规划解法
    动态规划的核心思想是 “分而治之” 和 “记住求过的解来节省时间”。
    定义状态：
    f[i] [j] 表示考虑前 i 个物品，在背包容量为 j 时可以获得的最大价值

状态转移方程：
对于第 i 个物品，我们有两种选择：

  1. 不选第 i 个物品：f[i] [j] = f[i-1] [j]
  2. 选第 i 个物品：f[i] [j] = f[i-1] [j-w[i] ] + v[i]

我们取这两种情况的最大值：
f[i] [j] = max{f[i-1][j], f[i-1] [j-w[i] ] +v[i] }

初始化：
f[0] [j] = 0 （0个物品时价值为0）
f[i] [0] = 0 （背包容量为0时价值为0）

具体例子：

  • 假设背包容量为6，每个物品只能选择取或者不取。
  • 物品：
    • 葡萄：w=2，v=3
    • 矿泉水：w=3，v=5
    • 西瓜：w=4，v=6
物品 容量w 价值v
葡萄 2 3
矿泉水 3 5
西瓜 4 6
构建DP表：
  • i 表示物品号
  • j 表示容量大小
  • 表内格子显示当考虑 物品 i 且背包容量为 j 时，背包内的最大价值
i\j 0 1 2 3 4 5 6
0 0 0 0 0 0 0 0
1 0 0 3 3 3 3 3
2 0 0 3 5 5 8 8
3 0 0 3 5 6 8 9

解释：

  • 第一行：没有物品时，背包价值为0
  • 第二行：只有物品1（葡萄），只要容量 大于等于2就能装下，价值为3
  • 第三行：可以考虑物品 1（葡萄）和 物品 2 （矿泉水）
    • j = 3时：可以选择物品2 （矿泉水 价值5）或者 不选 （价值 3） 取max(5, 3) = 5
    • j = 4时：可以选择物品2 （矿泉水 价值5）或者 不选 （价值 3） 取max(5, 3) = 5
    • j = 5时：可以选择物品 2 + 物品 1 (矿泉水 价值5 + 葡萄 价值3 = 8)或者不选 (矿泉水 价值5) 取max(8, 5 ) = 8
    • j = 6时：可以悬着物品 2 + 物品 1 (矿泉水 价值5 + 葡萄 价值3 = 8)或者不选 (矿泉水 价值5) 取max(8, 5) = 8
  • 第四行：考虑所有物品
    • j = 4时：可以选择物品3 （西瓜 价值6）或者不选（价值 5 ），取max(6,5) = 6
    • j = 6时：可以选择物品1 + 物品3(葡萄 价值3 + 西瓜 价值6 = 9) 或者不选 （价值8） ，取max(9,8) = 9

注释：
这里的不选是指，不选第 i 个物品，也就是当考虑第 i 个物品时，
当不选 第 i 个物品那么, 对应的最优解是前 i-1 个物品的最优解，
可以理解成与前一个解做比较，哪个更大留哪个

0-1背包问题解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
//C代码部分
#include <stdio.h>

#define max(a, b) ((a) > (b) ? (a) : (b))

int main(void) {
    int N = 3, V = 6;
    int w[] = {0,2,3,4};
    int v[] = {0,3,5,6};

    int f[N+ 1][V+ 1];
    for(int i = 0; i <= N; i++) {
        for(int j = 0; j <= V; j++) {
            f[i][j] = 0;
        }
    }

    for(int i = 1; i<= N; i++)
    {
        for(int j = 1; j <= V; j++)
        {
            if(j < w[i])
            {
                f[i][j] = f[i-1][j];
            }
            else
            {
                f[i][j] = max(f[i -1][j],f[i -1][j-w[i]] +v[i]);
            }
        }
    }

    printf("%d",f[N][V]);

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
//C++代码部分
#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    int N = 3 , V = 6;//物品数量为3 背包容量为6
    int w[] = {0,2,3,4};//物品占背包的容量
    int v[] = {0,3,5,6};//物品价值
    
    //int f[N+ 1][V+ 1] = {0};
    int f[N+ 1][V+ 1]; 
    for(int i = 0; i<= N; i++) {
        for(int j = 0; j <= V; j++) {
            f[i][j] = 0;
        }
    }
    
    for(int i = 1; i<= N; i++)
    {
        for(int j = 1; j <= V; j++)
        {
            if(j < w[i])
            {
                f[i][j] = f[i-1][j];
            }
            else
            {
                f[i][j] = max(f[i- 1][j],f[i- 1][j-w[i]]+ v[i]);
            }
        }
    }
    
    cout <<f[N][V] <<endl;
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#Python代码部分
def knapsack_01(N,V,w,v):
    #初始化dp表
    f = [[0] * (V + 1) for _ in range(N+ 1)]
    for i in range(1, N+ 1):
        for j in range(1, V+ 1):
            if j< w[i]:
                f[i][j] = f[i- 1][j]
            else:
                f[i][j] = max(f[i- 1][j], f[i-1][j-w[i]]+ v[i])
    return f[N][V]

def main():
    N = 3#物品数量
    V = 6#背包容量
    w = [0,2,3,4]#物品重量
    v = [0,3,5,6]#物品价值
    
    max_value = knapsack_01(N, V, w, v)
    print(f"背包能装下的最大价值为: {max_value}")

if __name__ == "__main__":
    main()
    
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
//JAVA
public class Knapsack01 {

    public static int knapsack(int numItems, int capacity, int[] weights, int[] values) {
        // 创建动态规划表
        int[][] dp = new int[numItems + 1][capacity + 1];

        // 填充动态规划表
        for (int i = 1; i <= numItems; i++) {
            for (int j = 1; j <= capacity; j++) {
                if (j < weights[i]) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weights[i]] + values[i]);
                }
            }
        }

        return dp[numItems][capacity];
    }

    public static void main(String[] args) {
        // 测试数据
        final int NUM_ITEMS = 3;
        final int CAPACITY = 6;
        int[] weights = {0, 2, 3, 4};  // 索引0不使用
        int[] values = {0, 3, 5, 6};    // 索引0不使用

        // 计算并输出结果
        int maxValue = knapsack(NUM_ITEMS, CAPACITY, weights, values);
        System.out.println("背包能装下的最大价值为: " + maxValue);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
//Rust代码部分
fn knapsack_01(num_items: usize, capacity: usize, weights: &[usize], values: &[usize]) -> usize {
    // 初始化动态规划表
    let mut dp = vec![vec![0; capacity + 1]; num_items + 1];

    //填充动态规划表
    for i in 1..=num_items 
    {
        for j in 1..=capacity 
        {
            if j < weights[i] 
            {
                dp[i][j] = dp[i - 1][j];
            } 
            else 
            {
                dp[i][j] = std::cmp::max(dp[i - 1][j], dp[i - 1][j - weights[i]] + values[i]);
            }
        }
    }

    dp[num_items][capacity]
}

fn main() {
    // 物品数量
    const NUM_ITEMS: usize = 3;
    // 背包容量
    const CAPACITY: usize = 6;
    // 物品重量
    let weights = vec![0, 2, 3, 4];
    // 物品价值
    let values = vec![0, 3, 5, 6];

    let max_value = knapsack_01(NUM_ITEMS, CAPACITY, &weights, &values);
    println!("背包能装下的最大价值为: {}", max_value);
}

完全背包问题

多重背包问题

混合背包问题

二维费用的背包问题

分组背包问题

背包问题求方案数

求背包问题的方案

有依赖的背包问题