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

🕗 发布于 2024-07-07 12:09 算法 c++ 动态规划 leetcode c语言

文章目录

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

在这里插入图片描述

❤️❤️❤️❤️❤️博客主页：lyyyyrics❤️❤️❤️❤️❤️
在这里插入图片描述

💗背包问题

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

输入：给定一个容量为 $W$ 的背包和 $n$ 个物品，每个物品 $i$ 有一个重量 $w_i$ 和一个价值 $v_i$ 。
目标：选择若干个物品放入背包，使得总重量不超过背包的容量 $W$ ，并且总价值最大化。

💛背包问题的变体

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

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

目标函数：
$\text{maximize} \sum_{i=1}^{n} c_i \cdot x_i$
其中， $n$ 表示物品的数量， $c_i$ 表示物品 $i$ 的价值。

约束条件：
$\sum_{i=1}^{n} w_i \cdot x_i \leq C$
其中， $w_i$ 表示物品 $i$ 的重量， $C$ 表示背包的容量。

其它约束条件：
$x_i \in \{0,1\}$
$1,2,3,\ldots,n$
其中， $x_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;
}

运行结果：
在这里插入图片描述

💗总结

通过对0/1背包问题的分析和动态规划解法的详细讲解，我们可以看到这种经典问题在算法设计中的重要性。0/1背包问题不仅是许多实际应用的基础，也是理解和掌握动态规划思想的一个重要实例。

在解决0/1背包问题时，关键在于构建状态转移方程并合理使用空间和时间资源。通过递归和迭代的方法，我们能更好地理解背包问题的解法，优化算法效率，并提升解决复杂问题的能力。

希望这篇博客能帮助你理解0/1背包问题的基本原理和解法，同时激发你对动态规划和算法设计的进一步兴趣和探索。未来的学习中，不妨尝试更多的变种背包问题和动态规划问题，以不断提升自己的算法技能和编程水平。

原文地址：https://blog.csdn.net/2301_79969994/article/details/140151022

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：Kylin系列（二）架构解析：深入理解 Kylin 的架构设计
下一篇：【ARMv8/v9 GIC 系列 5.6 -- GIC 超优先级中断详细介绍】

leetcode289:生命游戏
根据，简称为，是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。给定一个包含m × n个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态：1即为（live），或0即为
阅读更多2024-10-20
MongoDB数据恢复
注意：两个MongoDB的版本要一致，本文使用的是mongo:4.2.24。先把K8S上面的MongoDB 容器停止（可以把副本改成0）。1、将容器挂载MongoDB的数据目录备份到本地。经常是数据文
阅读更多2024-10-20
C#中实现事务
C#中实现事务
阅读更多2024-10-20
【LeetCode每日一题】——560.和为 K 的子数组
给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的子数组的个数。子数组是数组中元素的连续非空序列。
阅读更多2024-10-20
「漏洞复现」满客宝智慧食堂系统 selectUserByOrgId 未授权访问漏洞
请勿利用文章内的相关技术从事非法测试，由于传播、利用此文所提供的信息而造成的任何直接或者间接的后果及损失，均由使用者本人负责，作者不为此承担任何责任。工具来自网络，安全性自测，如有侵权请联系删除。本次
阅读更多2024-10-20
React面试题目（从基本到高级）
React前端面试常见题目涵盖了React的基础概念、组件、状态管理、生命周期、性能优化等多个方面。
阅读更多2024-10-20
12.个人博客系统（Java项目基于spring和vue）
1 在校学习的学生，可用于日常学习使用或是毕业设计使用 2 毕业一到两年的开发人员，用于锻炼自己的独立功能模块设计能力，增强代码编写能力。 3 亦可以部署为商化项目使用。 4 需要完整资料及源码
阅读更多2024-10-20
YoloV8改进策略：注意力改进|DeBiFormer，可变形双级路由注意力|引入DeBiLevelRoutingAttention注意力模块（全网首发）
本次改进的核心在于将DeBiLevelRoutingAttention模块嵌入到YoloV8的主干网络中，具体位置是在SPPF（Spatial Pyramid Pooling Fast）模块之后。这一
阅读更多2024-10-20
word取消自动单词首字母大写
情况说明：在word输入单词后首字母会自动变成大写取消单词首字母大写步骤：（1）点击菜单栏文件（2）点击“更多”——>“选项”（3）点击“校对”——>“自动更正选项”（4）取消“句首字母大
阅读更多2024-10-20
web前端网页用户注册页面
【代码】web前端网页用户注册页面。
阅读更多2024-10-20