题 d: 0-1 背包问题ytu C++代码

下面是0-1背包问题的C++代码实现：

#include <iostream>
#include <vector>
using namespace std;

int knapsack(int C, vector<int>& w, vector<int>& v) {
    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] = max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1]);
            }
            else {
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    return dp[n][C];
}

int main() {
    int C = 10;
    vector<int> w = {2, 3, 4, 5};
    vector<int> v = {3, 4, 5, 6};
    cout << "The maximum value of knapsack is " << knapsack(C, w, v) << endl;
    return 0;
}

其中，C表示背包的总容量，w表示物品的重量列表，v表示物品的价值列表。在函数中，我们首先定义一个二维数组dp来保存状态转移的结果。然后，我们依次遍历每一个物品，对于每一个物品，我们再依次遍历每一个容量，根据状态转移方程来更新dp数组。最后，函数返回dp[n][C]，即为背包所能装下物品的最大总价值。

需要注意的是，C++中的vector可以方便地实现动态数组，可以避免手动处理内存分配和释放的问题。