01背包问题代码

下面是01背包问题的动态规划代码实现，时间复杂度为O(nC)：

int knapsack(int C, int n, int w[], int v[]) {
    int dp[n+1][C+1];
    memset(dp, 0, sizeof(dp)); // 将dp数组初始化为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];
}

其中C为背包的容量，n为物品的数量，w数组存储每个物品的重量，v数组存储每个物品的价值。函数返回值为背包能够容纳的最大价值。