动态规划算法 例题 c++

这是一个使用动态规划算法解决 0/1 背包问题的例题：

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

const int MAXN = 100;
int n, m; // 物品数量和背包容量
int w[MAXN], v[MAXN]; // 物品的重量和价值
int dp[MAXN][MAXN]; // dp[i][j] 表示前 i 件物品放入容量为 j 的背包中所获得的最大价值

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

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (j < w[i]) { // 背包容量不足，无法放入第 i 件物品
                dp[i][j] = dp[i - 1][j];
            } else { // 可以选择放或不放第 i 件物品
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
            }
        }
    }

    cout << dp[n][m] << endl; // 输出最大价值
    return 0;
}

代码中使用了一个二维数组 `dp`，其中 `dp[i][j]` 表示前 i 件物品放入容量为 j 的背包中所获得的最大价值。根据 0/1 背包问题的定义，每个物品只能选择放或不放，因此状态转移方程为：

$$
dp[i][j]=\begin{cases}
dp[i-1][j] & j<w_i \\
\max(dp[i-1][j],dp[i-1][j-w_i]+v_i) & j\geq w_i
\end{cases}
$$

其中 $w_i$ 和 $v_i$ 分别表示第 $i$ 个物品的重量和价值，$dp[i-1][j]$ 表示不放第 $i$ 件物品的最大价值，$dp[i-1][j-w_i]+v_i$ 表示放第 $i$ 件物品的最大价值。最终，$dp[n][m]$ 即为所求的最大价值。