社区首页 >专栏 >DP：背包问题----0/1背包问题

DP：背包问题----0/1背包问题

用户11305458

发布于 2024-10-09 09:10:58

4060

文章被收录于专栏：学习学习

💗背包问题

背包问题（Knapsack Problem）是一类经典的组合优化问题，在计算机科学和数学中有广泛应用。其基本问题是：

输入：给定一个容量为

W

$W$

的背包和

n

$n$

个物品，每个物品

i

$i$

有一个重量

w_{i}

$w_i$

和一个价值

v_{i}

$v_i$

。

目标：选择若干个物品放入背包，使得总重量不超过背包的容量

W

$W$

，并且总价值最大化。

💛背包问题的变体

0/1 背包问题：每个物品只能选择一次，即要么选中（1）要么不选（0）。
分数背包问题：每个物品可以分割，即可以选择物品的一部分。
多重背包问题：每个物品有多个副本，可以选择多个相同的物品。
多维背包问题：背包有多个限制条件，例如容量和体积等。

🧡0/1 背包问题的数学定义

目标函数：

maximize n \sum i = 1 c_{i} \cdot x_{i}

$\text{maximize} \sum_{i=1}^{n} c_i \cdot x_i$

其中，

n

$n$

表示物品的数量，

c_{i}

$c_i$

表示物品

i

$i$

的价值。

约束条件：

n \sum i = 1 w_{i} \cdot x_{i} \leq C

$\sum_{i=1}^{n} w_i \cdot x_i \leq C$

其中，

w_{i}

$w_i$

表示物品

i

$i$

的重量，

C

$C$

表示背包的容量。

其它约束条件：

x_{i} \in {0, 1}

$x_i \in \{0,1\}$

i = 1, 2, 3, \dots, n

$i = 1,2,3,\ldots,n$

其中，

x_{i}

$x_i$

表示物品

i

$i$

是否被选中。

💚解决背包问题的方法

解决背包问题的方法有很多，包括动态规划、分支定界法、贪心算法（适用于分数背包问题）以及各种近似算法和启发式算法等。

💙例子

假设有一个背包容量为 50 的背包，有以下物品：

物品	重量	价值
1	10	60
2	20	100
3	30	120

目标是选择物品使得总重量不超过 50 且总价值最大化。在这个例子中，最佳选择是选取物品 2 和物品 3，总重量为 50，总价值为 220。

💗解决背包问题的一般步骤？

背包问题是一个经典的优化问题，可以通过动态规划算法来解决。下面是解决背包问题的一般步骤：

确定问题的约束条件：背包的容量限制和物品的重量和价值。
定义状态：将问题拆解为多个子问题，定义状态为背包的容量和可选择的物品。
定义状态转移方程：根据子问题的定义，确定状态之间的关系。例如，对于背包问题，可以定义状态转移方程为f(i,j)，表示在前i个物品中选择，背包容量为j时，可以获得的最大价值。则可以得到状态转移方程：f(i,j) = max(f(i-1,j), f(i-1,j-w[i])+v[i])，其中w[i]和v[i]分别表示第i个物品的重量和价值。
确定初始条件：确定边界条件，即背包容量为0时，价值为0。
通过动态规划算法计算最优解：根据状态转移方程和初始条件，利用循环或递归的方式计算最优解。
回溯最优解：根据计算得到的最优解，可以通过回溯的方式确定选择了哪些物品放入背包中，从而得到最终的解。

需要注意的是，背包问题的解决方法还包括贪心算法、分支界限算法等。具体选择哪种方法取决于问题的约束条件和需要优化的目标。

💗例题

题目链接 题目：

样例输出和输入：

这道题并不是leetcode的那种接口的模式，而是ACM模式，我们需要进行完整的输入和输出，我们先分析第一个样例：

0	1	2	3
容量	2	4	1
价值	10	5	4

第一个问题是给定一个背包容量，求出当背包的容量不用装满时的最大价值，意思就是我们选出的物品的总的容量可以小于背包的容量，也可以等于背包的容量，这时，我们可以第一个物品和三个物品的价值是最大的。总价值为14，第二个问题是我们必须将背包容量给塞满，求塞满的状态的物品的最大价值，这种情况下有可能是没有结果的，因为无法选出能将背包塞满的组合，所以这时候就输出零。但是这个例子是可以输出结果的，塞满的情况应该是第二个物品和第三个物品，总价值是9，所以最后输出14和9。

算法原理： 状态表示：dp[i][j]-----表示选到第i个位置时的所有选法中的不超过总容积j的最大价值。状态转移方程：

这是不把背包填满的情况下的状态转移方程，还有一个问题就是需要将背包填满。

所以这里如果要用到前一个状态的话，应该判断一下前一个状态是否是-1，如果前一个状态是-1的话，就表示这种情况根本不存在，所以不能选择这种状态

初始化：第一个问题的初始化只需要将dp表初始化为0，第二个问题的初始化上面已经讨论过了。填表顺序：也是按照从左上角到右下角，依次填表。返回值：返回dp[n][V] 代码展示：

#include <cstring>
#include <iostream>
#include<string>
using namespace std;

//数据范围
const int N = 1010;
//n个数据，V为背包的总容量，v表示单个物品的所占容积，w表示单个物品所含的价值
int n, V, v[N], w[N];
//i表示第i个位置，j表示总的容积
int dp[N][N];

int main()
{
    //输入总数据，和总容积
    cin >> n >> V;
    for (int i = 1;i <= n;i++)
    {
        cin >> v[i] >> w[i];
    }
    //解决第一问
    for (int i = 1;i <= n;i++)
    {
        //j表示容量
        for (int j = 1;j <= V;j++)
        {
            //不选的情况
            dp[i][j] = dp[i - 1][j];
            //如果能选，则和之前不选的情况求一个max
            if (j >= v[i])dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
        }
    }
    //输出最后一个dp状态
    cout << dp[n][V] << endl;
    //重置dp表，将表中数据重置为0
    memset(dp, 0, sizeof dp);
    //单独初始化第一排的后面的位置，因为如果没有任何物品根本不可能有价值，所以初始化为-1
    for (int i = 1;i <= V;i++)
    {
        //初始化不存在dp的位置
        dp[0][i] = -1;
    }
    for (int i = 1;i <= n;i++)
    {
        //j表示容量
        for (int j = 1;j <= V;j++)
        {
            //可以不选
            dp[i][j] = dp[i - 1][j];
            //如果要选择当前位置的话需要考虑前一个状态是否是-1，选不到的情况 
            if (j >= v[i] && dp[i - 1][j - v[i]] != -1)
                dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
        }
    }
    //如果不存在选满的情况，直接返回0，否则返回dp[n][V]位置的值
    cout << (dp[n][V] == -1 ? 0 : dp[n][V]) << endl;
    return 0;
}

代码优化： 可以利用滚动数组进行优化：

#include <cstring>
#include <iostream>
#include<string>
using namespace std;

//数据范围
const int N = 1010;
//n个数据，V为背包的总容量，v表示单个物品的所占容积，w表示单个物品所含的价值
int n, V, v[N], w[N];
//i表示第i个位置，j表示总的容积
int dp[N];

int main()
{
    //输入总数据，和总容积
    cin >> n >> V;
    for (int i = 1;i <= n;i++)
        cin >> v[i] >> w[i];
    //解决第一问
    for (int i = 1;i <= n;i++)
        //j表示容量
        for (int j = V;j >= v[i];j--)//修改遍历顺序
            //如果能选，则和之前不选的情况求一个max
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
    //输出最后一个dp状态
    cout << dp[V] << endl;
    //重置dp表，将表中数据重置为0
    memset(dp, 0, sizeof dp);
    //单独初始化第一排的后面的位置，因为如果没有任何物品根本不可能有价值，所以初始化为-1
    for (int i = 1;i <= V;i++)
        //初始化不存在dp的位置
        dp[i] = -1;
    for (int i = 1;i <= n;i++)
        //j表示容量
        for (int j = V;j >= v[i];j--)//修改遍历顺序
            //如果能选，则和之前不选的情况求一个max
            if(dp[j-v[i]]!=-1)
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
    //如果不存在选满的情况，直接返回0，否则返回dp[n][V]位置的值
    cout << (dp[V] == -1 ? 0 : dp[V]) << endl;
    return 0;
}