从背包家族说起

[linan04143 (Star lit Journey「y.t.x」)]

姓名： 俞天行
赛道： 普及组
类型： 算法技能

背包问题

关键词： 0/1 背包问题、完全背包问题、分数背包问题

一、引言

《背包赋》

• 吾尝问于编程间，
  何为背包，解未传。
  物品众多，各有重，
  价值相随，欲收攫。

• 定大小，容量有限，
  装满之法，岂易然？
  一纸算法，思维巧，
  动态规划，乃真仙。

• 复古自古，应用广，
  各类变种，繁且详。
  0/1背包，选择是，
  每物一件，难抉择。

• 遍历状态，更新朝，
  前者后者，决胜高。
  选与不选，分界清，
  逐步逼近，目标昭。

• 递归分支，尝试深，
  剪枝优化，智者婚。
  时间复杂，操控间，
  教材理论，收获甚。

• 此道何需愁与望？
  数据结构，知识广。
  如若献身，研磨久，
  背包问题，终有王。

• 哦，编程世界无尽头，
  巧手解难，乐无忧。
  背包在心，理于手，
  携带价值，奔前仆。

背包问题是计算机科学与运筹学中一个经典的优化问题，广泛应用于资源分配、调度等多个领域。在 C++ 中，该问题通常涉及使用数组、动态规划、递归等技术来寻找解决方案。

背包王国

在 \color{brown}{山的那边} ， \color{teal}{海的那边} ，有 一群蓝精灵 一个奇特的王国——背包王国，我是你背包王国的导游，带你领略这里的山川美景。

背包王国中有三个部落，分别是：
0/1 背包问题部落、完全背包问题部落、分数背包问题部落
\color{green}{like} \color{green}{this} →

图好看吧？自己手打的

1. 0/1 背包问题（0/1 Knapsack Problem）：每种物品只能选择一次。给定每件物品的重量和价值，以及背包的最大承载重量，目标是最大化放入背包的物品总价值。
2. 完全背包问题（Complete Knapsack Problem）：每种物品可以选择多次。类似于 0/1 背包，但可以重复选择物品。
3. 分数背包问题（Fractional Knapsack Problem）：可以选择任何物品的部分。给定每件物品的单位重量价值，允许我们选择物品的一部分以获得最大总价值。

二、数学模型

1.0/1背包问题数学模型

0/1背包问题是一个经典的组合优化问题，属于NP完全类别，常用于计算机科学、运筹学和优化领域。它的数学模型可以可以通过以下要素描述：

问题描述

物品及其属性：

有 n 种物品，每种物品 i 的重量为 w_i ( i = 1, 2, \ldots, n )。
每种物品 i 的价值为 v_i 。

背包及其属性：

背包的最大承重(容量)为 W ，这个值是固定不变的。

目标

目标是在不超过背包容量 W 的前提下，选择物品，使得总价值最大。与完全背包问题不同，在0/1背包中，每种物品只能选择一次(即0次或1次)。

数学模型

该问题可以通过以下数学模型来描述：

(1)决策变量：

设 x_i 为决策变量，表示是否选择物品 i :
x_i = 1 表示选择物品 i
x_i = 0 表示不选择物品 i
因此， x_i 是一个二元变量。

(2)目标函数：

最大化总价值： \max Z = \sum_{i=1}^n v_i x_i

(3)约束条件：

确保背包容量不被超出： \sum_{i=1}^n w_i x_i \leq W

(4)非负约束：

所有决策变量必须是二值： x_i \in {0, 1} \quad i = 1, 2, \ldots, n
所有决策变量都必须非负整数： x_i \geq 0 \quad i = 1, 2, \ldots; n

(5)例子

举个简单的例子：

假设有 3 种物品：
物品 1: w_1 = 2, v_1 = 3
物品 2: w_2 = 1, v_2 = 2
物品 3: w_3 = 3, v_3 = 4
背包容量 W = 5

综上所述，0/1背包问题的数学模型可以表示为：

\begin{align*} \text{Maximize } & Z = \sum_{i=1}^{n} v_i x_i \ \text{Subject to } & \sum_{i=1}^{n} w_i x_i \leq W \ & x_i \in {0, 1}, \quad \text{for } i = 1, 2, \ldots, n \end{align*}

2.完全背包问题数学模型

定义：

• 设有 ( n ) 个物品，每个物品 i 的重量为 w_i ，( i = 1, 2, \ldots, n )，价值为 v_i 。
• 背包的最大承载重量为 $ W $。

决策变量：

• 设 x_i 为非负整数变量，表示放入背包的物品 i 的数量。

目标函数：

• 最大化总价值： \text{Maximize } Z = \sum_{i=1}^{n} v_i x_i

约束条件：

• 总重量不超过背包的最大承载重量： \sum_{i=1}^{n} w_i x_i \leq W
• 决策变量限制： x_i \geq 0 \quad \text{且 } x_i \text{ 为整数}, \quad \text{for } i = 1, 2, \ldots, n

综上所述，完全背包问题的数学模型可以表示为：

\begin{align*} \text{Maximize } & Z = \sum_{i=1}^{n} v_i x_i \ \text{Subject to } & \sum_{i=1}^{n} w_i x_i \leq W \ & x_i \geq 0 \quad \text{且 } x_i \text{ 为整数}, \quad \text{for } i = 1, 2, \ldots, n \end{align*}

3.分数背包问题数学模型

分数背包问题是一种特殊类型的背包问题，它允许你选择物品的任意部分，也就是说，你可以根据需要将物品分割成任意大小的部分放入背包。这使得分数背包问题与0/1背包问题和完全背包问题具有显著的不同。

定义：

• 设有 n 个物品，每个物品 i 的重量为 w_i ( i = 1, 2, \ldots, n ) ，价值为 v_i 。
• 背包的最大承载重量为 W 。

决策变量：

• 设 x_i 为变量，表示放入背包的物品 i 的数量 或分数 ，其中 0 \leq x_i \leq 1 表示选择物品的比例。

目标函数：

• 最大化总价值： \text{Maximize } Z = \sum_{i=1}^{n} v_i x_i

约束条件：

• 总重量不超过背包的最大承载重量： \sum_{i=1}^{n} w_i x_i \leq W
• 决策变量限制： 0 \leq x_i \leq 1, \quad \text{for } i = 1, 2, \ldots, n

综上所述，分数背包问题的数学模型可以表示为:

\begin{align*} \text{Maximize } & Z = \sum_{i=1}^{n} v_i x_i \ \text{Subject to } & \sum_{i=1}^{n} w_i x_i \leq W \ & 0 \leq x_i \leq 1, \quad \text{for } i = 1, 2, \ldots, n \end{align*}

三、解决问题

状态转移方程

状态转移，顾名思义，就是从一个状态迈向另一个状态的过程；一个连续的过程，一个函数的极限，物理的机械决定，天体的运行预测，都是通过上一个状态而影响下一个状态，由上一个状态而决定下一个个状态。

• 01背包的状态转移方程是 dp[i][j]=dp[i - 1][j]+dp[i - 1][j - v[i]];

• 完全背包的状态转移方程是 dp[i][j]=dp[i-1][j]+dp[i][j-v[i]];

• 分数背包的状态转移方程是 dp[i][j]=max(dp[i - 1][j], dp[i - 1][j - w[i]])

• 多重背包的状态转移方程是 dp[i][j]=\sum_{k=0}^{\min(c[i],j/v[i])}dp[i-k\cdot v[i]]; （这个后面会讲的）

  • ( 边界： dp[0][0]=1 )

0/1 背包问题

0/1背包问题是一个经典的组合优化问题，它主要描述了这样一种场景：你有一个背包，这个背包的容量是有限的，同时你面前有一系列的物品，每个物品有自己的重量和价值。问题在于，你如何从这些物品中选择一些装入背包，使得背包中物品的总价值最大，同时不超过背包的容量限制。

问题定义

假设我们有n个物品，第i个物品的重量是wi，价值是vi。我们有一个背包，其容量为W。0/1背包问题要求我们找到一个最优解，即选择哪些物品装入背包，使得背包中物品的总价值最大，同时不超过背包的容量限制。

解决方法

0/1背包问题可以通过动态规划来解决。动态规划是一种通过将问题分解为更小的子问题来求解的方法，它避免了重复计算，提高了效率。

1. 定义状态：

• 用 dp[i][w] 表示前 i 件物品放入容量为 w 的背包中能够获得的最大价值。

2. 状态转移方程：

• 如果不放入第 i 件物品：dp[i][w] = dp[i-1][w]
• 如果放入第 i 件物品（前提是 w >= weight[i-1]）：

dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight[i-1]] + value[i-1])

• 如果dp为一维数组，那么可以表示为：

dp[i] = max(dp[i], dp[i - weight[i]] + value[i]);

3. 初始化：

• dp[0][w] = 0 代表没有物品时的最大值都是0。
• dp[i][0] = 0 代表背包容量为0时的最大值也都是0。

4. 动态规划一般解题思路

for (int i = 1; i <= n; i++) { //遍历i个商品
    for (int j = m; j >= w[i]; j--) {
    //m就是背包最大容量
         //状态转移方程
    }
}

5. 结果：

• dp[n][capacity] 会存储放入容量为 capacity 的背包时可以获得的最大价值。

栗子

假设背包容量W=10，有3个物品，物品1的重量w1=2，价值v1=3；物品2的重量w2=3，价值v2=4；物品3的重量w3=4，价值v3=5。我们可以通过动态规划的方法来解决这个问题。

• 1. 初始化dp数组，dp[3][10]，所有元素初始值为0。
• 2. 从左到右，从上到下，按照状态转移方程计算dp数组的每个值。
• 3. 最终，dp[3][10]的值即为最大价值。

0/1背包问题的解决不仅展示了动态规划的强大，还体现了问题分解和子问题重用的思想，是算法学习中的一个经典案例。

来试试水

01背包问题示例

例题 NOIP2005-J-3-采药

1. NOIP2005-J-3-采药

题目ID：1478 必做题100分

最新提交：

Accepted

100 分

历史最高：

Accepted

100 分

时间限制: 1000ms

空间限制: 262144kB

题目描述

时间限制：1s 空间限制：256M

题目描述：

松下问童子，言师采药去，云深不知处，只在此山中

辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”

如果你是辰辰，你能完成这个任务吗？

输入格式：

第一行有两个整数T（1 ≤ T ≤ 1000）和M（1 ≤ M ≤ 100），用一个空格隔开，T代表总共能够用来采药的时间，M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之间（包括1和100）的整数，分别表示采摘某株草药的时间和这株草药的价值。

输出格式：

包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。

样例输入：

70 3 
71 100 
69 1 
1 2

样例输出：

3

数据范围：

对于30%的数据，M ≤ 10；
对于全部的数据，M ≤ 100。

这题就是一道0/1背包问题的经典例题，来看一下它的解题思路和伪代码

    for(int i = 0; i < M; i++) {
       //输入重量与价值
       for(int j = T; j >= w; j--) { //T就是背包最大容量
			//状态转移方程
       }
    }
    
    //输出，注意：输出dp的第T项

---

完全背包问题

完全背包问题与 0/1 背包问题的区别

• 完全背包问题：每种物品可以选择无限次，即 ( x[i] ) 可以是任意非负整数。
• 0/1 背包问题：每种物品只能选择一次，即 ( x[i] ) 只能是 0 或 1。

动态规划

对于背包问题的解决，我们通常使用动态规划（Dynamic Programming）。我们定义一个状态数组 ( dp[j] )，表示容量为 ( j ) 的背包所能获得的最大价值。

1. 初始化：

• dp[0] = 0 (当背包容量为0时，最大价值为0)
• dp[j] = 0 对所有 1 \leq j \leq C

2. 状态转移方程： 对于每种物品 ( i )（从 1 到 ( n )），我们根据物品的重量进行更新：
   dp[j] = \max(dp[j], dp[j - w[i]] + v[i]) \quad \text{对于每件物品 i, 当 } j \geq w[i]
   这表示对于每一容量 j ，我们要么不选择第 i 件物品（保持原本的最大价值），要么选择它并增加它的价值（并减少它的重量）。

物理解释

从物理的角度来看，背包问题可以理解为“能量”的优化问题：

• 价值可以视为“能量”或“功能”，即为了获得更多的好处（价值或能量），需要在背包中选择合适的物品。
• 重量可以视为“代价”或“耗费”，每种物品都有其消耗的部分，导致背包的总重量限制。选择多种物品时，必须考虑其总重量是否小于背包容量。

背包问题不仅仅是数字的优化，也涉及到如何最佳利用有限资源。例如，选择最佳的物品组合以最大化收益或效能。通过定义状态、约束和目标，我们可以通过动态规划轻松解决这些问题并找到最优解。

状态转移方程：

dp[i][w] = max(dp[i-1][w], dp[i][w - weight[i-1]] + value[i-1]);

\color{red}{延伸} →

多重背包问题 ‌

与完全背包不同，多重背包中的每种物品有一定的数量限制。解决这类问题的一种策略是将问题转化为0/1背包问题即每种物品只有一个。这可以通过将物品的数量按照二进制划分，然后将这些划分后的物品看作是独立的0/1背包问题中的物品来解决。这种方法的关键在于将物品的数量划分为2的幂次方倍的数量和剩余的数量，然后对每一部分分别使用0/1背包的解法进行处理。

\color{blue}{SO}

状态转移方程

dp[j] = max(dp[j], dp[j - value[i]] + weight[i])

---

分数背包问题

分数背包问题采用贪心策略。详情如下：

为了求解分数背包问题，我们首先来定义一个物品的价值密度（Value Density），它是物品的价值与其重量之比：

\text{价值密度} = \frac{v_i}{w_i}

接下来，解决方案的步骤如下：

1. 计算每个物品的价值密度：对于每个物品 i ，计算 d_i = \frac{value[i]}{weight[i]} 。
2. 按价值密度排序：将物品按价值密度从高到低排序。这意味着优先处理价值密度更高的物品。
3. 选择物品：初始化背包的当前重量为0，当前价值为0，然后遍历排序后的物品列表：

• 如果当前物品的重量可以完全放入背包（当前重量 + 物品重量 ≤ W），则将整个物品放入背包。
• 如果当前物品的重量超过了剩余的背包容量，你可以放入这个物品的一部分。计算可以放入的重量，并根据价值密度计算增加的价值。

4. 停止条件：当背包满或者所有物品都处理完毕时停止。

---

总结

背包问题是一个经典的算法问题，不同版本的背包问题使用不同的算法。0/1 背包问题适合动态规划，完全背包问题也可以通过动态规划来处理，而分数背包问题则可以使用贪心算法。在实际应用中，选择合适的方法来解决特定问题是非常重要的。

---

by： linan04143 (俞天行) ，如有建议或文章内容有误，请在评论区指出，谢谢

[linan04143 (Star lit Journey「y.t.x」)]

？？？

[linan04143 (Star lit Journey「y.t.x」)]

有没有大佬有意见啊

[linan04129 (蔡老师)]

有啊

[linan04129 (蔡老师)]

这不是基础组的吗 @linan04143

[王薪宇]

latex怎么炸了

[linan04143 (Star lit Journey「y.t.x」)]

刷新下

[王薪宇]

OK

[jhxs988 (洛谷又双叒叕日爆了！)]

@linan04143

三把手应该是递推吧

[linan04143 (Star lit Journey「y.t.x」)]

我真服了呀翻老帖，我就想这么写，咋了

[linan04129 (蔡老师)]

不翻老帖别人怎么给你点赞 @linan04143

[linan04143 (Star lit Journey「y.t.x」)]

emm…

说得好！