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;
}
以上代码即为动态规划解决背包问题的实现过程。
原文地址: https://www.cveoy.top/t/topic/ju7p 著作权归作者所有。请勿转载和采集!