0-1背包问题-c语言实现

价值v[]={0,1,6,18,22,28}

重量w[]={0,1,2,5,6,7}

背包容量T=11

上面是求最大价值公式，不是很容易看懂

下面图文是具体求最大价值的步骤：

c语言实现

动态规划-递归方法

自顶向下

#include 

//0-1背包问题

#define N 6  //
#define maxT 100
int c[N][maxT] = {0};

int Memoized_Knapspsack(int v[N], int w[N], int T);
int Calculate_Max_Value(int v[N], int w[N], int i, int j);

int Memoized_Knapspsack(int v[N], int w[N], int T){
    int i,j;
    for (i = 0; i < N; i++)
    {
        for (j = 0; j < T; j++)
        {
            c[i][j] = -1;
        }
    }
    return Calculate_Max_Value(v, w, N-1, T);
    
}

int Map_Knapspsack(int v[N], int w[N], int T){
    int i,j;
    
    for (i = 0; i < N; i++)
    {
        for (j = 0; j < T+1; j++)
        {
            printf("%2d   ", Calculate_Max_Value(v, w, i, j));
        }
        printf("n");
    }
    
    
}

int Calculate_Max_Value(int v[N], int w[N], int i, int j){
    int temp = 0;
    if(i == 0 || j == 0){
        c[i][j] = 0;
    }else{
        c[i][j] = Calculate_Max_Value(v, w, i-1, j);  //1.
        if(i > 0 && j >= w[i]){  //当j < w[i]时c[i][j]一定是等于c[i-1][j]
            temp = Calculate_Max_Value(v, w, i-1, j-w[i]) + v[i];  //2.
            if(temp > c[i][j]){
                c[i][j] = temp;  //3.
            }
        }
    }
    return c[i][j];
}

int main(void){
    int v[] = {0,1,6,18,22,28};
    int w[] = {0,1,2,5,6,7};
    int T = 11;
    int result = Memoized_Knapspsack(v, w, T);
    printf("最大价值 = %dn", result);
    Map_Knapspsack(v, w, T);
    return 0;
}

结果