用C++举例说明动态规划

动态规划（Dynamic Programming）是一种常用的算法思想，它通常用来解决一些重复计算的问题，通过将问题分解成更小的子问题，避免了重复计算，从而提高了算法的效率。

下面以一个经典的背包问题为例，来说明动态规划的实现过程。

问题描述：

有一个背包，它的容量为C，有n个物品，每个物品有一个重量w和一个价值v，现在需要从这n个物品中选取一些放入背包中，使得所选物品的总重量不超过C，且总价值最大。

解决方案：

定义一个二维数组dp[i][j]，表示前i个物品中选取一些放入容量为j的背包中所能获得的最大价值。则有以下状态转移方程：

dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i])

其中，dp[i-1][j]表示不选第i个物品，dp[i-1][j-w[i]]+v[i]表示选第i个物品，此时背包容量需要减去w[i]，并加上v[i]的价值。

最终的答案即为dp[n][C]。

C++代码实现：

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

const int MAXN = 1005;
int n, C, w[MAXN], v[MAXN], dp[MAXN][MAXN];

int main() {
    cin >> n >> C;
    for (int i = 1; i <= n; ++i) cin >> w[i] >> v[i];

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

    cout << dp[n][C] << endl;
    return 0;
}

以上代码即为动态规划解决背包问题的实现过程。