01背包问题（动态规划法，C语言）

#include
int Max(int n1,int n2){
    if(n1>n2){
        return n1;
    }
    return n2;
}
int main(){
    int n=6,c=12;
    int value[]={0,6,3,5,4,3,6};
    int weight[]={0,4,6,2,2,5,3};
    int m[n+1][c+1];
    for(int i=0;i<=n;i++){
        for(int j=0;j<=c;j++){
            m[i][j]=0;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=c;j++){
            if(j>=weight[i]){
                m[i][j]=Max(m[i-1][j],m[i-1][j-weight[i]]+value[i]);
            }else{
                m[i][j]=m[i-1][j];
            }
        }
    }
    printf("背包物品总价值最大为:%dn",m[n][c]);
    int trace[n+1];
    for(int i=n;i>=1;i--){
        if(c<0){
            printf("errorn");
            break;
        }
        if(m[i][c]==m[i-1][c]){
            trace[i]=0;
        }else{
            trace[i]=1;
            c-=weight[i];
        }
    }
    printf("此时背包内物品有(1表示有，0表示没有，从左到右依次为第i个物品状态):n");
    for(int i=1;i<=n;i++){
        printf("%dt",trace[i]);
    }
    return 0;
}