c++背包

背包问题是一类经典的组合优化问题，通常用于解决在有限容量下如何选择物品以最大化总价值的问题。根据物品是否可以分割，背包问题可以分为以下几类： - **0/1 背包问题**：物品不可分割，只能选择放入或不放入，通常使用**动态规划**（Dynamic Programming）求解。 - **完全背包问题**：每种物品可以无限次选取，使用**动态规划**求解时，与 0/1 背包的唯一区别在于遍历顺序的不同。 - **多重背包问题**：每种物品有固定数量，可以通过优化转化为 0/1 背包或使用二进制拆分优化。 - **分组背包问题**：每一组物品中只能选择一个，通常使用三层循环（组、容量、组内物品）来处理。 - **混合背包问题**：包含多种类型的物品（如 0/1、完全、多重），需要综合处理。 ### 0/1 背包问题的 C++ 实现 以下是一个典型的 0/1 背包问题的 C++ 实现，使用了动态规划方法： ```cpp #include <iostream> #include <vector> using namespace std; int knapsack(int capacity, const vector<int>& weights, const vector<int>& values) { int n = weights.size(); vector<vector<int>> dp(n + 1, vector<int>(capacity + 1, 0)); for (int i = 1; i <= n; ++i) { for (int j = 0; j <= capacity; ++j) { if (weights[i - 1] <= j) { dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1]); } else { dp[i][j] = dp[i - 1][j]; } } } return dp[n][capacity]; } int main() { vector<int> weights = {2, 3, 4, 5}; vector<int> values = {3, 4, 5, 6}; int capacity = 8; int result = knapsack(capacity, weights, values); cout << "Maximum value: " << result << endl; return 0; } ``` ### 完全背包问题的 C++ 实现 完全背包允许物品重复选取，因此在动态规划中采用**正向遍历**的方式： ```cpp #include <iostream> #include <vector> using namespace std; int unboundedKnapsack(int capacity, const vector<int>& weights, const vector<int>& values) { int n = weights.size(); vector<int> dp(capacity + 1, 0); for (int i = 0; i < n; ++i) { for (int j = weights[i]; j <= capacity; ++j) { dp[j] = max(dp[j], dp[j - weights[i]] + values[i]); } } return dp[capacity]; } int main() { vector<int> weights = {2, 3, 4, 5}; vector<int> values = {3, 4, 5, 6}; int capacity = 8; int result = unboundedKnapsack(capacity, weights, values); cout << "Maximum value (unbounded): " << result << endl; return 0; } ``` ### 多重背包问题的 C++ 实现 多重背包问题中，每种物品有固定数量，可以通过**二进制拆分**优化，将其转化为 0/1 背包问题： ```cpp #include <iostream> #include <vector> using namespace std; int multipleKnapsack(int capacity, const vector<int>& weights, const vector<int>& values, const vector<int>& quantities) { int n = weights.size(); vector<int> dp(capacity + 1, 0); for (int i = 0; i < n; ++i) { int count = quantities[i]; int w = weights[i]; int v = values[i]; // 二进制拆分 int k = 1; while (count >= k) { int weight = w * k; int value = v * k; for (int j = capacity; j >= weight; --j) { dp[j] = max(dp[j], dp[j - weight] + value); } count -= k; k <<= 1; } if (count > 0) { int weight = w * count; int value = v * count; for (int j = capacity; j >= weight; --j) { dp[j] = max(dp[j], dp[j - weight] + value); } } } return dp[capacity]; } int main() { vector<int> weights = {2, 3, 4}; vector<int> values = {3, 4, 5}; vector<int> quantities = {3, 2, 1}; int capacity = 10; int result = multipleKnapsack(capacity, weights, values, quantities); cout << "Maximum value (multiple): " << result << endl; return 0; } ``` ### 分组背包问题的 C++ 实现 分组背包问题中，每组物品只能选择一个，通常使用三层循环（组、容量、组内物品）来处理： ```cpp #include <iostream> #include <vector> using namespace std; int groupedKnapsack(int capacity, const vector<vector<int>>& weights, const vector<vector<int>>& values) { int groupCount = weights.size(); vector<int> dp(capacity + 1, 0); for (int g = 0; g < groupCount; ++g) { int itemCount = weights[g].size(); for (int j = capacity; j >= 0; --j) { for (int k = 0; k < itemCount; ++k) { if (j >= weights[g][k]) { dp[j] = max(dp[j], dp[j - weights[g][k]] + values[g][k]); } } } } return dp[capacity]; } int main() { vector<vector<int>> weights = {{2, 3}, {4, 5}, {6, 7}}; vector<vector<int>> values = {{3, 4}, {5, 6}, {7, 8}}; int capacity = 10; int result = groupedKnapsack(capacity, weights, values); cout << "Maximum value (grouped): " << result << endl; return 0; } ``` ### 总结 背包问题的解法主要依赖于动态规划和贪心策略，具体实现方式因问题类型而异： - **0/1 背包**：使用二维或一维动态规划表，逆序遍历容量。 - **完全背包**：使用一维动态规划表，正序遍历容量。 - **多重背包**：通过二进制拆分优化，转化为 0/1 背包。 - **分组背包**：在每组中选择最优物品，三层循环处理。 这些算法在实际应用中非常广泛，例如资源分配、投资组合优化、任务调度等领域。