[数据结构与算法]01背包问题（动态规划法，C语言）

#include<stdio.h>
int Max(int n1,int n2){
    if(n1>n2){
        return n1;
    }
    return n2;
}
int main(){
    int n=6,c=12;/*6个物品，背包容量为12*/
    int value[]={0,6,3,5,4,3,6};/*物品价值，从下标1开始*/
    int weight[]={0,4,6,2,2,5,3};/*物品重量，从下表1开始*/
    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]){/*j为当前总空间，j>=weight[i]表示第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("背包物品总价值最大为:%d\n",m[n][c]);
    int trace[n+1];
    for(int i=n;i>=1;i--){/*追踪具体装了哪几个物品*/
        if(c<0){
            printf("error\n");
            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("%d\t",trace[i]);
    }
    return 0;
}