0/1背包问题动态规划算法c++代码

以下是0/1背包问题动态规划算法的C++代码：

#include <iostream>
using namespace std;

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

int main() {
    int n = 5;
    int c = 10;
    int w[] = {2, 2, 6, 5, 4};
    int v[] = {6, 3, 5, 4, 6};
    cout << knapsack(w, v, n, c) << endl; // 输出为15
    return 0;
}

其中，`dp[i][j]`表示在前`i`个物品中选择不超过容量为`j`的背包的最大价值，`w[]`表示物品的重量，`v[]`表示物品的价值，`n`表示物品的个数，`c`表示背包的容量。