动态规划c++代码实例
时间: 2023-03-19 18:21:23 浏览: 48
动态规划是一种常用的解决计算机科学问题的方法,其目的是通过分治、重复计算和存储结果来减少计算量,并找到最优解。
下面是一个用 C 语言实现的动态规划代码示例,它求解了一个简单的背包问题:
```
#include <stdio.h>
#include <stdlib.h>
#define N 5
#define M 11
int w[N] = {0, 2, 2, 6, 5};
int v[N] = {0, 6, 3, 5, 4};
int f[N][M];
int max(int a, int b) {
return a > b ? a : b;
}
int main() {
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
if (j < w[i]) {
f[i][j] = f[i - 1][j];
} else {
f[i][j] = max(f[i - 1][j], f[i - 1][j - w[i]] + v[i]);
}
}
}
printf("最大价值:%d\n", f[N][M]);
return 0;
}
```
该代码模拟了一个背包的过程,其中有 5 件物品,每件物品的体积分别为 w[1..5],每件物品的价值分别为 v[1..5]。它计算出了当背包容量为 11 时的最大价值,并在控制台输出了结果。