当前位置：首页 > news >正文

【C++】01背包问题暴力，记忆，动态规划解法

news 来源：原创 2024/9/19 13:35:00

0-1 背包问题详解与实现

问题描述

在算法领域，0-1背包问题是一个经典的优化问题。给定一个背包和一个物品集合，每个物品有其重量和价值，我们需要选择物品放入背包，使得背包内物品的总价值最大，同时不超过背包的容量限制。

问题分析

0-1背包问题可以通过决策树模型来理解。每件物品都有放入或不放入背包的选择，我们可以定义状态来描述这一决策过程。

状态定义

状态[i, c]：考虑前i个物品，在容量为c的背包中能获得的最大价值。

状态转移方程

不放入物品i：dp[i, c] = dp[i-1, c]
放入物品i：dp[i, c] = dp[i-1, c-wgt[i-1]] + val[i-1]
最终状态dp[n, cap]即为所求的最大价值。

边界条件

当无物品或背包容量为0时，最大价值为0。

算法实现

我们可以通过递归、记忆化搜索和动态规划三种方式来解决0-1背包问题。

暴力搜索

int bag01(vector<int>& wgt, vector<int>& val, int i, int c) {if (i == 0 || c == 0) return 0;if (wgt[i - 1] > c) return bag01(wgt, val, i - 1, c);int no = bag01(wgt, val, i - 1, c);int yes = bag01(wgt, val, i - 1, c - wgt[i - 1]) + val[i - 1];return max(no, yes);
}

记忆化搜索

int bag01Mem(vector<int>& wgt, vector<int>& val, vector<vector<int>>& mem, int i, int c) {if (i == 0 || c == 0) return 0;if (mem[i][c] != -1) return mem[i][c];if (wgt[i - 1] > c) return bag01Mem(wgt, val, mem, i - 1, c);int no = bag01Mem(wgt, val, mem, i - 1, c);int yes = bag01Mem(wgt, val, mem, i - 1, c - wgt[i - 1]) + val[i - 1];mem[i][c] = max(no, yes);return mem[i][c];
}

动态规划

int bag01DP(vector<int>& wgt, vector<int>& val, int cap) {int n = wgt.size();vector<vector<int>> dp(n + 1, vector<int>(cap + 1, 0));for (int i = 1; i <= n; i++) {for (int c = 1; c <= cap; c++) {if (wgt[i - 1] > c) {dp[i][c] = dp[i - 1][c];} else {dp[i][c] = max(dp[i - 1][c], dp[i - 1][c - wgt[i - 1]] + val[i - 1]);}}}return dp[n][cap];
}

空间优化

通过倒序遍历和去除第一维，我们可以优化空间复杂度。

int bag01DPm(vector<int>& wgt, vector<int>& val, int cap) {int n = wgt.size();vector<int> dp(cap + 1, 0);for (int i = 1; i <= n; i++) {for (int c = cap; c >= 1; c--) {if (wgt[i - 1] <= c) {dp[c] = max(dp[c], dp[c - wgt[i - 1]] + val[i - 1]);}}}return dp[cap];
}

总结

0-1背包问题是算法学习中的一个重要问题，通过不同的方法实现，我们可以更好地理解递归、记忆化搜索和动态规划的概念和应用。

思维导图

下面是0-1背包问题的思维导图，展示了不同算法之间的关系和转换过程。

C++学习资源

以下是我学C++觉得不错的资料，仅供学习：
匠心精作C++从0到1入门编程-学习编程不再难
链接: https://pan.baidu.com/s/1q7NG28V8IKMDGD7CMTn2Lg?pwd=ZYNB 提取码: ZYNB
第二套、侯捷老师全系列八部曲 - 手把手教你进阶系列
链接: https://pan.baidu.com/s/1AYzdguXzbaVZFw1tY6rYJQ?pwd=ZYNB 提取码: ZYNB