c++01背包问题。有n 个物品，它们有各自的重量和价值，现有给定容量为c的背包，如何让背包里装入的物品具有最大的价值总和？ 要求：输入物品个数，背包容量，以及各物品的重量和价值，输出其动态规划表，以及最优值和最优解

在C++01中解决背包问题通常使用动态规划方法。这个问题属于0-1背包问题，常见于贪心算法和最优化问题。以下是基本步骤：

1. 定义状态：设`dp[i][j]`表示前i个物品中选择总重量不超过j的最大价值。

2. 初始化：对于每个物品i，若`j`小于该物品的重量`weight[i]`，则`dp[i][j] = dp[i-1][j]`；否则，我们可以选择包含或不包含这个物品，所以`dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i])`。

3. 动态规划表构建：从第一个物品开始，遍历所有可能的重量范围，逐步更新`dp`数组。

4. 结果获取：最终的最优解即`dp[n][c]`，其中`n`是物品数量，`c`是背包容量。

5. 可选路径恢复：如果需要找到具体的最优解，可以回溯到`dp[n][c]`对应的`dp[i][j-weight[i]]`，因为这是包含当前物品的选择。

下面是一个简单的C++代码示例（假设已有一个结构体Item存储每个物品的重量value）：

#include <vector>
using namespace std;

struct Item {
    int weight;
    int value;
};

int knapsack(vector<Item>& items, int capacity) {
    vector<vector<int>> dp(items.size() + 1, vector<int>(capacity + 1));
    
    for (int i = 1; i <= items.size(); ++i) {
        for (int j = 1; j <= capacity; ++j) {
            if (items[i - 1].weight <= j) {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - items[i - 1].weight] + items[i - 1].value);
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }

    return dp[items.size()][capacity];
}

void printDP(vector<vector<int>>& dp, int n, int c) {
    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j <= c; ++j) {
            cout << dp[i][j] << " ";
        }
        cout << endl;
    }
}