各种动态规划算法的C语言_c语言动态规划

以下是常见的几种动态规划算法的C语言实例：

1. 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;
}

1. 完全背包问题

#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 =