01背包问题（不装满和装满）和完全背包问题

🕗 发布于 2024-12-08 04:42 c++ 动态规划算法

本文将详细讲解 01背包问题 和 完全背包问题，包括问题定义、思路分析、状态转移方程以及代码实现。

01背包问题

问题定义

给定一个容量为 V 的背包，有 N 件物品，每件物品有一个体积 w[i] 和一个价值 v[i]。每种物品只能选择 0次或1次。求如何选择物品，使得装入背包的物品总价值最大。

解题思路

01背包问题是经典的动态规划问题，主要思路是 逐件考虑是否选择当前物品。

状态定义

用 dp[j] 表示在背包容量为 j 时，能得到的最大价值。

状态转移方程

如果不选择第 i 件物品：dp[j] = dp[j]（容量和价值都不变）。
如果选择第 i 件物品：dp[j] = dp[j - w[i]] + v[i]（容量减少 w[i]，价值增加 v[i]）。
综合考虑：dp[j] = max(dp[j], dp[j - w[i]] + v[i])。

初始化

dp[0] = 0：容量为0时，最大价值为0。
其他 dp[j] 初始化为0（或负无穷，视题目要求而定）。

优化

由于每件物品只能用一次，物品需从大到小枚举容量 j（避免重复选择）。

代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int N, V;
    cin >> N >> V;

    vector<int> w(N + 1), v(N + 1);
    for (int i = 1; i <= N; ++i) {
        cin >> w[i] >> v[i];
    }

    vector<int> dp(V + 1, 0);

    // 使用动态规划求解
    for (int i = 1; i <= N; ++i) { // 枚举每件物品
        for (int j = V; j >= w[i]; --j) { // 从大到小枚举容量
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }

    cout << dp[V] << endl; // 输出容量为V时的最大价值
    return 0;
}

完全背包问题

问题定义

与01背包类似，给定一个容量为 V 的背包，有 N 件物品，每件物品有一个体积 w[i] 和一个价值 v[i]。但是每种物品可以选择 无限次。求如何选择物品，使得装入背包的物品总价值最大。

解题思路

完全背包问题的核心区别在于，每种物品可以选择多次。状态转移和01背包类似，但在计算状态时，要允许重复选择同一件物品。

状态定义

用 dp[j] 表示在背包容量为 j 时，能得到的最大价值。

状态转移方程

如果选择第 i 件物品：dp[j] = dp[j - w[i]] + v[i]（容量减少 w[i]，价值增加 v[i]）。
如果不选择第 i 件物品：dp[j] = dp[j]。
综合考虑：dp[j] = max(dp[j], dp[j - w[i]] + v[i])。

优化

由于每件物品可以重复选择，容量 j 应从小到大枚举（确保当前容量的状态可以多次使用同一件物品）。

代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int N, V;
    cin >> N >> V;

    vector<int> w(N + 1), v(N + 1);
    for (int i = 1; i <= N; ++i) {
        cin >> w[i] >> v[i];
    }

    vector<int> dp(V + 1, 0);

    // 使用动态规划求解
    for (int i = 1; i <= N; ++i) { // 枚举每件物品
        for (int j = w[i]; j <= V; ++j) { // 从小到大枚举容量
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }

    cout << dp[V] << endl; // 输出容量为V时的最大价值
    return 0;
}

两者对比

特性	01背包问题	完全背包问题
物品使用次数	每件物品最多使用一次	每件物品可以使用无限次
容量枚举顺序	从大到小（避免重复选择同一件物品）	从小到大（允许重复选择同一件物品）
状态转移公式	`dp[j] = max(dp[j], dp[j - w[i]] + v[i])`	`dp[j] = max(dp[j], dp[j - w[i]] + v[i])`

装满的01背包

下面将详细讲解 恰好装满背包问题 和 物品有依赖关系的背包问题，包括问题定义、思路分析、状态转移方程、以及代码实现。

问题定义

给定一个容量为 V 的背包，有 N 件物品，每件物品有体积 w[i] 和价值 v[i]。每种物品只能使用一次。求如何选择物品，使得 恰好装满背包 的情况下，背包中的总价值最大。如果无法恰好装满背包，输出 0。

与普通 01 背包的区别

普通 01 背包：只需要背包容量不超过 V，即可保证结果有效。
恰好装满背包：必须严格要求背包容量 正好等于 V，否则结果无效。

解题思路

动态规划的核心思想还是类似于 01 背包，但需要特别处理 恰好装满 的约束。

状态定义

定义 dp[j] 表示：容量为 j 的背包，所能装下的最大价值。
- 如果背包容量 恰好装满，dp[V] 就是答案。
- 如果无法恰好装满背包，则 dp[V] 的值为无效状态。

状态转移方程

如果不选第 i 件物品：
dp[j] = dp[j]（容量和价值都不变）。
如果选第 i 件物品：
dp[j] = dp[j - w[i]] + v[i]（减少容量，增加价值）。
综合考虑：
dp[j] = max(dp[j], dp[j - w[i]] + v[i])。

特殊处理：无效状态

初始时，dp[j] = -∞（表示无效状态），只有 dp[0] = 0（容量为 0 时的初始状态有效）。
最终结果如果 dp[V] == -∞，说明无法恰好装满背包。

初始化

dp[0] = 0：容量为 0 时，背包价值为 0。
其他 dp[j] 初始化为负无穷（-∞），表示初始时无效状态。

代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int N, V;
    cin >> N >> V;

    vector<int> w(N + 1), v(N + 1);
    for (int i = 1; i <= N; ++i) {
        cin >> w[i] >> v[i];
    }

    vector<int> dp(V + 1, -1e9); // 初始化为无穷小
    dp[0] = 0; // 容量为 0 时，价值为 0

    // 动态规划过程
    for (int i = 1; i <= N; ++i) { // 枚举每件物品
        for (int j = V; j >= w[i]; --j) { // 从大到小枚举容量
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }

    // 输出结果
    if (dp[V] < 0) {
        cout << 0 << endl; // 无法恰好装满背包
    } else {
        cout << dp[V] << endl; // 恰好装满时的最大价值
    }

    return 0;
}

举例

输入：

N = 3, V = 5
物品 1: w = 1, v = 2
物品 2: w = 3, v = 4
物品 3: w = 4, v = 5

输出：

解释：

恰好装满容量为 5 的背包，选择物品 1 和物品 2，总价值为 6。

物品有依赖关系的背包问题

问题定义

给定一个容量为 V 的背包，有 N 件物品，每件物品有体积 w[i] 和价值 v[i]。此外，每件物品还有一个附加属性 parent[i]：

如果 parent[i] = 0，表示该物品是一个 主物品。
如果 parent[i] > 0，表示该物品是 从属于第 parent[i] 件物品的附件。

要求

如果选择了某个附件物品，必须先选择它的主物品。
一个主物品最多可以选择 2 个附件。

解题思路

这是一个 树形依赖的多重背包问题，可以通过 分组背包 的思想解决：

将每个主物品及其附件看作一个组。
每个组内的状态转移，枚举主物品和附件的组合情况。

状态定义

定义 dp[j] 表示：容量为 j 的背包，所能装下的最大价值。

状态转移方程

对于每个主物品及其附件，枚举所有可能的组合：
- 只选主物品
- 选主物品 + 一个附件
- 选主物品 + 两个附件
更新状态 dp[j]。

分组处理

遍历所有物品，将主物品及其附件分组。
对每一组物品，枚举容量 j 和组合情况，更新 dp[j]。

代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Item {
    int w, v; // 物品的体积和价值
    int parent; // 主从关系
};

int main() {
    int N, V;
    cin >> N >> V;

    vector<Item> items(N + 1);
    for (int i = 1; i <= N; ++i) {
        cin >> items[i].w >> items[i].v >> items[i].parent;
    }

    vector<int> dp(V + 1, 0);

    // 遍历所有主物品
    for (int i = 1; i <= N; ++i) {
        if (items[i].parent == 0) { // 主物品
            vector<pair<int, int>> group; // 当前组
            group.push_back({items[i].w, items[i].v}); // 主物品加入组

            // 找到所有附件
            for (int j = 1; j <= N; ++j) {
                if (items[j].parent == i) {
                    group.push_back({items[j].w, items[j].v});
                }
            }

            // 处理当前组
            for (int j = V; j >= 0; --j) { // 从大到小枚举容量
                for (auto& item : group) { // 枚举组内所有物品
                    if (j >= item.first) {
                        dp[j] = max(dp[j], dp[j - item.first] + item.second);
                    }
                }
            }
        }
    }

    cout << dp[V] << endl;
    return 0;
}

举例

输入：

N = 5, V = 10
物品 1: w = 5, v = 10, parent = 0 (主物品)
物品 2: w = 4, v = 7, parent = 1 (附件)
物品 3: w = 3, v = 6, parent = 1 (附件)
物品 4: w = 6, v = 12, parent = 0 (主物品)
物品 5: w = 2, v = 4, parent = 4 (附件)

输出：

解释：

选择主物品 1 和它的附件（物品 3），主物品 4 和它的附件（物品 5），总价值为 23。

总结

恰好装满背包问题：用 -∞ 初始化，动态规划时确保状态只更新到恰好装满的容量。
物品有依赖关系的背包问题：将主物品和附件分组，枚举组内的组合情况，动态更新状态。

扩展知识

多重背包问题：每种物品有一个限制使用次数的上限，可以将每种物品拆分成若干个01背包问题来解决，或者用二进制优化。
混合背包问题：有的物品是01背包，有的是完全背包，甚至有的是多重背包。
背包问题变种：比如要求恰好装满背包、物品有依赖关系等。

如果你有其他问题，欢迎随时提问！

原文地址：https://blog.csdn.net/2303_80261633/article/details/144300351

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

上一篇：# issue 9 进程
下一篇：【go 】 select case 的用法

.NET(C#) 如何配置用户首选项及保存用户设置
.NET(C#) 如何配置用户首选项及保存用户设置
阅读更多2024-12-14
【最新】北大数字普惠金融指数数据集-省市县（2011-2023年）
郭峰,王靖一,王芳,孔涛,张勋,程志云.测度中国数字普惠金融发展:指数编制与空间特征[J].经济学(季刊),2020,19(04):1401-1418.时间跨度：省级和城市级指数时间跨度为2011-2
阅读更多2024-12-14
GESP202412 四级【Recamán】题解（AC）
a11ak−1−kkakak−1−kak−1k小杨想知道 Recamán 数列的前n项从小到大排序后的结果。手动计算非常困难，小杨希望你能帮他解决这个问题。
阅读更多2024-12-14
IDEA遇到EasyConnect中的网络资源无法访问的问题
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。原文链接：https://blog.csdn.net/wanshanyu_/article/de
阅读更多2024-12-14
双目摄像头标定方法
此时已经完成标定，左下角为反投影误差，右边为外参可视化。将双目左右目拍的图像上传（左右目最好不少于20张）此时回到主页面，即可看到成功导出。把这些误差大的删除即可。
阅读更多2024-12-14
Servlet、omcat服务器架构与工作原理
Servlet是运行在服务器端的Java程序，它的主要职责之一是接收并处理来自客户端（如浏览器）的HTTP请求。当客户端发送一个请求到服务器时，Servlet可以解析请求中的信息，例如请求的URL路径
阅读更多2024-12-14
Vue生命周期钩子函数：深入解析与实践
作为高级Vue前端开发人员，对Vue组件的生命周期钩子函数有着深刻的理解是至关重要的。生命周期钩子函数是指在Vue组件的创建、更新、销毁等过程中，Vue自动调用的一系列方法。通过这些钩子函数，我们可以
阅读更多2024-12-14
安卓开发--使用android studio发布APP
app发布
阅读更多2024-12-14
数据结构与算法学习笔记----拓扑排序
@ author: 明月清了个风。
阅读更多2024-12-14
python 将数据保存到现有的Excel文件的新工作表
out_file = ‘query.xlsx’df1 = pd.DataFrame(out_data)若直接写入：df1.to_excel(out_file, index=False, sheet_n
阅读更多2024-12-14

01背包问题（不装满和装满）和完全背包问题

01背包问题

问题定义

解题思路

状态定义

状态转移方程

初始化

优化

代码实现

完全背包问题

问题定义

解题思路

状态定义

状态转移方程

优化

代码实现

两者对比

装满的01背包

问题定义

与普通 01 背包的区别

解题思路

状态定义

状态转移方程

特殊处理：无效状态

初始化

代码实现

举例

输入：

输出：

解释：

物品有依赖关系的背包问题

问题定义

要求

解题思路

状态定义

状态转移方程

分组处理

代码实现

举例

输入：

输出：

解释：

总结

扩展知识

相关文章