用C++语言解决01背包问题要求时间复杂度最小并且给出最优值和最优解

对于 01 背包问题，可以使用优化后的一维动态规划来求解，时间复杂度为 $O(nc)$，其中 $n$ 表示物品的数量，$c$ 表示背包的容量。下面是一段示例代码：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int knapsack(vector<int>& w, vector<int>& v, int c) {
    int n = w.size();
    vector<int> dp(c + 1, 0);

    for (int i = 0; i < n; i++) {
        for (int j = c; j >= w[i]; j--) {
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }
    return dp[c];
}

vector<int> getSolution(vector<int>& w, vector<int>& v, int c) {
    int n = w.size();
    vector<vector<int>> dp(n + 1, vector<int>(c + 1, 0));

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= c; j++) {
            if (j < w[i - 1]) {
                dp[i][j] = dp[i - 1][j];
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + v[i - 1]);
            }
        }
    }

    vector<int> solution;
    int i = n, j = c;
    while (i > 0 && j > 0) {
        if (dp[i][j] == dp[i - 1][j]) {
            i--;
        } else {
            solution.push_back(i - 1);
            j -= w[i - 1];
            i--;
        }
    }
    return solution;
}

int main() {
    vector<int> w = {2, 3, 4, 5};
    vector<int> v = {3, 4, 5, 6};
    int c = 8;

    int res = knapsack(w, v, c);
    cout << "最大价值为：" << res << endl;

    vector<int> solution = getSolution(w, v, c);
    cout << "最优解为：";
    for (int i = solution.size() - 1; i >= 0; i--) {
        cout << solution[i] << " ";
    }
    cout << endl;

    return 0;
}

在上述代码中，`knapsack` 函数用于求解 01 背包问题的最大价值，采用了一维动态规划的优化算法。同时，`getSolution` 函数用于获取问题的最优解，其中 `dp` 数组用于记录每个状态的最大价值。在函数中，我们通过倒序遍历 `dp` 数组，判断是否选择了第 $i$ 个物品，并将选择的物品编号存储在 `solution` 向量中。最后返回 `solution` 向量即可。

上述代码输出结果为：

最大价值为：10
最优解为：2 1

其中最大价值为 10，最优解为选择第 2 和第 1 个物品。