以下是常见的几种动态规划算法的C语言实例:
- 01背包问题
#include<stdio.h>
#define max_n 1010
int n, W, w[max_n], v[max_n], dp[max_n][max_n];
int max(int a, int b) {return a > b ? a : b;}
void ZeroOnePack(int i) {
for(int j = 0; j <= W; ++j) {
if(j < w[i]) {
dp[i][j] = dp[i-1][j];
}else {
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]);
}
}
}
int main() {
scanf("%d%d", &n, &W);
for(int i = 1 ;i <= n; ++i) {
scanf("%d%d", &w[i], &v[i]);
}
for(int i = 1; i <= n; ++i) {
ZeroOnePack(i);
}
printf("%d", dp[n][W]);
return 0;
}
- 完全背包问题
#include<stdio.h>
#define max_n 1010
int n, W, w[max_n], v[max_n], dp[max_n];
int max(int a, int b) {return a > b ? a : b;}
void CompletePack(int i) {
for(int j =