有n个重量分别为w={w_1,w_2,…,w_n}的物品，他们的价值分别为v={v_1,v_2,…,v_n}，给定一个容量为v的背包。 设计从这些物品中选取一部分物品放入该背包的方案，每个物品要么选中要么不选中，要求选中的物品不仅能够放到背包中，并且背包内物品的总价值达到最大。 输入格式 第一行输入两个整数n、g，其中n表示物品的数量，g表示背包的容量体积。 第二行输入n个整数，整数间以空格分隔，表示n个物品的重量w_i 第三行输入n个整数，整数间以空格分隔，表示n个物品的价值v_i 输出格式 第一行输出最大价值是v，v是计算得到的背包内物品总价值的最大值 第二行输出最大价值共有k种选择方案,分别是:，k是最大价值时，背包内物品选择的方案总数。 随后k行输出选择第x1 x2 ... xn个物品，x1、x2、...xn、是选择的第几个物品，中间以空格分隔，输出顺序以字典序排序。

这是一个经典的背包问题，可以使用动态规划来求解。 定义一个二维数组dp，其中dp[i][j]表示前i个物品放入容量为j的背包中能够获得的最大总价值。 初始化dp数组的第一列和第一行都为0。 对于第i个物品，有两种情况： 1. 不选取第i个物品：dp[i][j] = dp[i-1][j]，表示前i-1个物品放入容量为j的背包中能够获得的最大总价值。 2. 选取第i个物品：dp[i][j] = dp[i-1][j-w[i]] + v[i]，表示将第i个物品放入容量为j的背包中能够获得的最大总价值。 状态转移方程为： dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]) 最终，dp[n][g]就是背包内物品的最大总价值。 然后，通过回溯的方式，找出所有的选择方案。从dp[n][g]开始向前遍历，如果dp[i][g] == dp[i-1][g]，说明第i个物品没有被选取；如果dp[i][g] == dp[i-1][g-w[i]] + v[i]，说明第i个物品被选取。递归回溯过程中，同时记录所有选择方案。 输出最大总价值和选择方案的数量，以及每个选择方案。 具体实现代码如下： ```cpp #include <iostream> #include <vector> #include <algorithm> using namespace std; vector<vector<int>> result; void backtrack(vector<vector<int>>& dp, vector<int>& w, vector<int>& v, int i, int j, vector<int>& cur) { if (i == 0) { result.push_back(cur); return; } if (dp[i][j] == dp[i-1][j]) { backtrack(dp, w, v, i-1, j, cur); } if (j >= w[i]) { if (dp[i][j] == dp[i-1][j-w[i]] + v[i]) { cur.push_back(i); backtrack(dp, w, v, i-1, j-w[i], cur); cur.pop_back(); } } } int main() { int n, g; cin >> n >> g; vector<int> w(n+1); vector<int> v(n+1); for (int i = 1; i <= n; i++) { cin >> w[i]; } for (int i = 1; i <= n; i++) { cin >> v[i]; } vector<vector<int>> dp(n+1, vector<int>(g+1, 0)); for (int i = 1; i <= n; i++) { for (int j = 1; j <= g; j++) { if (j >= w[i]) { dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]); } else { dp[i][j] = dp[i-1][j]; } } } cout << dp[n][g] << endl; vector<int> cur; backtrack(dp, w, v, n, g, cur); sort(result.begin(), result.end()); cout << result.size() << endl; for (auto& r : result) { for (int i = 0; i < r.size(); i++) { cout << r[i]; if (i != r.size() - 1) { cout << " "; } } cout << endl; } return 0; } ``` 时间复杂度分析： 动态规划部分的时间复杂度为O(n*g)，回溯部分的时间复杂度取决于选择方案的数量，最坏情况下为O(2^n)。总体时间复杂度为O(n*g + 2^n)。 [2024-06-09 15:51:05 | AI写代码神器 | 1709点数解答]